HDU - 3251 Being a Hero

Being a Hero

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1822 Accepted Submission(s): 625
Special 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
2
4 4 2
1 2 2
1 3 3
3 2 4
2 4 1
2 3
4 4
4 4 2
1 2 2
1 3 3
3 2 1
2 4 1
2 3
4 4

Sample Output
Case 1: 3
1 4
Case 2: 4
2 1 3

建图最小割，因为不能到达我们选的点，很明显就是对选的点的集合进行最小割，如果这个点不选，那么相当于就是割掉了这个点到汇点的一条流。

考虑建图：

• 能选的点向汇点连边，流量为选的价值
• 按照输入建图

还有一个问题就是输出最小割的割边。

我们对每个点染色，若此边流量为正，则让此边的下一个点染色。

最后判断每条边两端颜色即可，若颜色不同则为最小割的边。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1e4+10,M=1e6+10;
int T,n,m,f,h[N],s,t,vis[N];
int head[N],nex[M],to[M],w[M],tot;
inline void ade(int a,int b,int c){
	to[++tot]=b; nex[tot]=head[a]; w[tot]=c; head[a]=tot;
}
inline void add(int a,int b,int c){
	ade(a,b,c);	ade(b,a,0);
}
int bfs(){
	memset(h,0,sizeof h);	h[s]=1;	queue<int> q;	q.push(s);
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(w[i]&&!h[to[i]]){
				h[to[i]]=h[u]+1;	q.push(to[i]);
			}
		}
	}
	return h[t];
}
int dfs(int x,int f){
	if(x==t)	return f;
	int fl=0;
	for(int i=head[x];i&&f;i=nex[i]){
		if(w[i]&&h[to[i]]==h[x]+1){
			int mi=dfs(to[i],min(w[i],f));
			w[i]-=mi; w[i^1]+=mi; fl+=mi; f-=mi;
		}
	}
	if(!fl)	h[x]=-1;
	return fl;
}
inline int dinic(){
	int res=0;
	while(bfs())	res+=dfs(s,inf);
	return res;
}
void dfs1(int x){
	vis[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(w[i]>0&&!vis[to[i]])	dfs1(to[i]);
	}
}
inline void solve(int i){
	tot=1;	memset(head,0,sizeof head);	
	int res=0;	memset(vis,0,sizeof vis);
	scanf("%d %d %d",&n,&m,&f);	t=n+1; s=1;
	for(int i=1;i<=m;i++){
		int a,b,c;	scanf("%d %d %d",&a,&b,&c);	add(a,b,c);
	}
	for(int i=1;i<=f;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,t,b);	res+=b;
	}
	printf("Case %d: %d\n",i,res-dinic());
	vector<int> v;	dfs1(1);	v.clear();
	for(int i=2;i<=tot;i+=2){
		if(!vis[to[i]]&&vis[to[i^1]]&&i<=2*m)	v.push_back(i/2);
	}
	printf("%d",v.size());
	for(int i=0;i<v.size();i++)	printf(" %d",v[i]);
	puts("");
}
signed main(){
	cin>>T;
	for(int i=1;i<=T;i++)	solve(i);
	return 0;
}