Being a HeroTime Limit: 20000/10000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1229Accepted Submission(s): 387Special Judge
Problem Description
You are the hero who saved your country. As promised, the king will give you some cities of the country, and you can choose which ones to own!But don’t get too excited. The cities you take should NOT be reachable from the capital — the king does not want to accidentally enter your area. In order to satisfy this condition, you have to destroy some roads. What’s worse, you have to pay for that — each road is associated with some positive cost. That is, your final income is the total value of the cities you take, minus the total cost of destroyed roads.Note that each road is a unidirectional, i.e only one direction is available. Some cities are reserved for the king, so you cannot take any of them even if they’re unreachable from the capital. The capital city is always the city number 1.
Input
The first line contains a single integer T (T <= 20), the number of test cases. Each case begins with three integers n, m, f (1 <= f < n <= 1000, 1 <= m < 100000), the number of cities, number of roads, and number of cities that you can take. Cities are numbered 1 to n. Each of the following m lines contains three integers u, v, w, denoting a road from city u to city v, with cost w. Each of the following f lines contains two integers u and w, denoting an available city u, with value w.
Output
For each test case, print the case number and the best final income in the first line. In the second line, print e, the number of roads you should destroy, followed by e integers, the IDs of the destroyed roads. Roads are numbered 1 to m in the same order they appear in the input. If there are more than one solution, any one will do.
Sample Input
24 4 21 2 21 3 33 2 42 4 12 34 44 4 21 2 21 3 33 2 12 4 12 34 4
Sample Output
Case 1: 31 4Case 2: 42 1 3
Source
2009 Asia Regional Ningbo Online
这个题目可以用最小割来做，原图上的边的费用当成容量，另外将每个可以选择的点和T连起来，容量为点权，这样做完最小割之后就会将点分成两个集合，一部分是S出发能到达的，记作S集合，另一部分是能够到达T的点，记作T集合。这样如果可以选择的点属于了S集合，那么就必然要断开和T连的边，表示如果不选这个点那么相对与最大收益来讲就要减去这个点的点权，另外连通S集合和T集合的边也都要断开，表示为了从1出发不能到达T集合中选择的点，所需要付出的代价。
于是最后用理想的最大收益减去最小割就是可能获得的最大收益了。
打印割边的时候，可以先从S出发沿非满流的边走，能够走到的点都视作S集合中的点，那么剩下的点就可以看作是T集合中的点，这是连通S集合和T集合的边就一定是割边了。
#include<stdio.h>#include<string.h>#include<queue>#include<algorithm>using namespace std;#define captype intconst int MAXN = 100010; //点的总数const int MAXM = 400010; //边的总数const int INF = 1<<30;struct EDG{int to,next;captype cap,flow;} edg[MAXM];int eid,head[MAXN];int gap[MAXN]; //每种距离(或可认为是高度)点的个数int dis[MAXN]; //每个点到终点eNode 的最短距离int cur[MAXN]; //cur[u] 表示从u点出发可流经 cur[u] 号边int pre[MAXN];void init(){eid=0;memset(head,-1,sizeof(head));}//有向边 三个参数，无向边4个参数void addEdg(int u,int v,captype c,captype rc=0){edg[eid].to=v; edg[eid].next=head[u];edg[eid].cap=c; edg[eid].flow=0; head[u]=eid++;edg[eid].to=u; edg[eid].next=head[v];edg[eid].cap=rc; edg[eid].flow=0; head[v]=eid++;}captype maxFlow_sap(int sNode,int eNode, int n){//n是包括源点和汇点的总点个数，这个一定要注意memset(gap,0,sizeof(gap));memset(dis,0,sizeof(dis));memcpy(cur,head,sizeof(head));pre[sNode] = -1;gap[0]=n;captype ans=0; //最大流int u=sNode;while(dis[sNode]<n){ //判断从sNode点有没有流向下一个相邻的点if(u==eNode){ //找到一条可增流的路captype Min=INF ;int inser;for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]) //从这条可增流的路找到最多可增的流量Minif(Min>edg[i].cap-edg[i].flow){Min=edg[i].cap-edg[i].flow;inser=i;}for(int i=pre[u]; i!=-1; i=pre[edg[i^1].to]){edg[i].flow+=Min;edg[i^1].flow-=Min; //可回流的边的流量}ans+=Min;u=edg[inser^1].to;continue;}bool flag = false; //判断能否从u点出发可往相邻点流int v;for(int i=cur[u]; i!=-1; i=edg[i].next){v=edg[i].to;if(edg[i].cap-edg[i].flow>0 && dis[u]==dis[v]+1){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}//如果上面没有找到一个可流的相邻点，则改变出发点u的距离（也可认为是高度）为相邻可流点的最小距离+1int Mind= n;for(int i=head[u]; i!=-1; i=edg[i].next)if(edg[i].cap-edg[i].flow>0 && Mind>dis[edg[i].to]){Mind=dis[edg[i].to];cur[u]=i;}gap[dis[u]]–;if(gap[dis[u]]==0) return ans; //当dis[u]这种距离的点没有了，也就不可能从源点出发找到一条增广流路径//因为汇点到当前点的距离只有一种，那么从源点到汇点必然经过当前点，，然而当前点又没能找到可流向的点，那么必然断流dis[u]=Mind+1;//如果找到一个可流的相邻点，则距离为相邻点距离+1，如果找不到，则为n+1gap[dis[u]]++;if(u!=sNode) u=edg[pre[u]^1].to; //退一条边}return ans;}bool flag[MAXN];void bfs(int s){queue<int>q;memset(flag,0,sizeof(flag));flag[s]=1;q.push(s);while(!q.empty()){int u=q.front(); q.pop();for(int i=head[u]; i!=-1; i=edg[i].next)if(edg[i].cap-edg[i].flow>0&&flag[edg[i].to]==false){flag[edg[i].to]=true; q.push(edg[i].to);}}}int main(){int T,_cas=0,n,m,f,u,v,w;scanf("%d",&T);while(T–){init();scanf("%d%d%d",&n,&m,&f);int sum=0 , VS=1 , VT=n+1;for(int i=0; i<m; i++){scanf("%d%d%d",&u,&v,&w);addEdg(u,v,w);}while(f–){scanf("%d%d",&u,&w);addEdg(u,VT,w);sum+=w;}sum-=maxFlow_sap(VS,VT,VT);printf("Case %d: %d\n",++_cas,sum);bfs(VS);int num=0;for(int i=0; i<m*2; i+=2)if(flag[edg[i^1].to]&&!flag[edg[i].to])num++;printf("%d",num);for(int i=0; i<m*2; i+=2)if(flag[edg[i^1].to]&&!flag[edg[i].to])printf(" %d",i/2+1);printf("\n");}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
尝到你和你在一起的快乐，你是唯一能让我尝到酸甜苦辣的人。
