Cyclic Tour

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 3353 Accepted Submission(s): 1756

Problem Description
There are N cities in our country, and M one-way roads connecting them. Now Little Tom wants to make several cyclic tours, which satisfy that, each cycle contain at least two cities, and each city belongs to one cycle exactly. Tom wants the total length of all the tours minimum, but he is too lazy to calculate. Can you help him?

Input
There are several test cases in the input. You should process to the end of file (EOF).
The first line of each test case contains two integers N (N ≤ 100) and M, indicating the number of cities and the number of roads. The M lines followed, each of them contains three numbers A, B, and C, indicating that there is a road from city A to city B, whose length is C. (1 ≤ A,B ≤ N, A ≠ B, 1 ≤ C ≤ 1000).

Output
Output one number for each test case, indicating the minimum length of all the tours. If there are no such tours, output -1.

Sample Input
6 9
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
6 5
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1

Sample Output
42
-1

Hint
In the first sample, there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42.

Author
RoBa@TJU

题意：让我们找几个环包含所有点，然后每个点只能用一次，使得我们所有走的路径的距离最小。

结论：如果给定一张有向图，里面所有的点的入度和出度都为1，那么该图一定是由若干个不相交的环构成的。

我们可以想到用费用流。因为和最小路径覆盖很像。

考虑建图：

  • S向每个点的入点连边，流量为1，费用为0，限流每个点用一次。
  • 每个点的出点向T连边，流量为1，费用为0
  • 对于每个存在的边a->b，让a的入点连向b的出点，流量为1，费用为边权。

然后跑一次最大费用流即可。若流量不为n，则输出-1。如果流量为n，那么每个点都有出度，且都有入度则必成环。

所以建图正确。

AC代码：

#pragma GCC optimize
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int inf=0x3f3f3f3f;
const int N=1010,M=100010;
int n,m,v[N],e[N],d[N],s,t,res;
int head[N],nex[M],to[M],w[M],flow[M],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
inline bool spfa(){
	int vis[N]={0};	vis[s]=1;	queue<int> q;	q.push(s);
	memset(d,inf,sizeof d);	d[s]=0;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u;	e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
inline int EK(){
	int maxflow=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		maxflow+=mi;	res+=d[t]*mi;		
	}
	return maxflow==n;
}
signed main(){
	while(~scanf("%d %d",&n,&m)){
		t=2*n+1;	tot=1;	res=0;	memset(head,0,sizeof head);
		for(int i=1;i<=n;i++)	add(s,i,1,0),add(i+n,t,1,0);
		while(m--){
			int a,b,c;	scanf("%d %d %d",&a,&b,&c);	
			add(a,b+n,inf,c);	
		}
		printf("%d\n",EK()?res:-1);
	}
	return 0;
}