2015
04-13

# Base Station

A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is Pi (1<=i<=n).

When complete building, two places which both have stations can communicate with each other.

Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers Ai, Bi and Ci, which means if place Ai and Bi can communicate with each other, the company will get Ci profit.

Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.

Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0<n<=5000) and m (0<m<=50000).
The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.

Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0<n<=5000) and m (0<m<=50000).
The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3

4

#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 60000              //点的个数
#define INF 1e8
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
struct edge
{
int u,v,w,next;
}E[400050];                     //边的个数  记得乘2
int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN];
int l,r,mid;
int N,M,scr,sink,vn,num;
void Insert(int u,int v,int w)
{
E[ecnt].u=u;
E[ecnt].v=v;
E[ecnt].w=w;
E[ecnt].u=v;
E[ecnt].v=u;
E[ecnt].w=0;
}
int Sap(int s,int t,int n)//核心代码(模版)
{
int ans=0,aug=INF;//aug表示增广路的流量
int i,v,u=pre[s]=s;
for(i=0;i<=n;i++)
{
dis[i]=gap[i]=0;
}
gap[s]=n;
bool flag;
while(dis[s]<n)
{
flag=false;
for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定义成int &j,why
{
v=E[j].v;
if(E[j].w>0&&dis[u]==dis[v]+1)
{
flag=true;//找到容许边
aug=min(aug,E[j].w);
pre[v]=u;
u=v;
if(u==t)
{
ans+=aug;
while(u!=s)
{
u=pre[u];
E[cur[u]].w-=aug;
E[cur[u]^1].w+=aug;//注意
}
aug=INF;
}
break;//找到一条就退出
}
}
if(flag) continue;
int mindis=n;
{
v=E[i].v;
if(E[i].w>0&&dis[v]<mindis)
{
mindis=dis[v];
cur[u]=i;
}
}
if((--gap[dis[u]])==0) break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return ans;
}
int n,m;
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
scr=0;sink=n+m+1;vn=sink+1;
for(int i=1;i<=n;i++)
{
int v;
scanf("%d",&v);
Insert(i,sink,v);
}
int sum=0;
for(int i=1;i<=m;i++)
{
int a,b,v;
scanf("%d%d%d",&a,&b,&v);
Insert(scr,i+n,v);
Insert(i+n,a,INF);
Insert(i+n,b,INF);
sum+=v;
}
printf("%d\n",sum-Sap(scr,sink,vn));
}
return 0;
}


1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
O(n) = O(n-1) + O(n-2) + ….
O(n-1) = O(n-2) + O(n-3)+ …
O(n) – O(n-1) = O(n-1)
O(n) = 2O(n-1)

2. 可以参考算法导论中的时间戳。就是结束访问时间，最后结束的顶点肯定是入度为0的顶点，因为DFS要回溯

3. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1