Cyclic Tour
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Total Submission(s): 92 Accepted Submission(s): 50
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).
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 -1HintIn 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
Source
Recommend
lcy
真的刚开始没想到这道题目能用费用流去做啊。。。。
后来看了大牛的题解才想到
几个很关键的条件
1.每个点只属于一个回路，并且所有点必须都属于回路
2.每个回路必须要有两个以上的点
3.要是回路总的费用最小
这几个条件限制了这题的解法
可以是KM,为了让KM算法更熟悉一点，明天就会上KM的解题报告
说说最小费用流的构图方法吧
首先是设立两个超级源点汇点S，T
S向每个点连边，容量为1，费用为0，限制的是每个点的入度
T和每个I+N连边，容量为1，费用为0，限制的是每个点的出度
这样就满足了第一个条件，就是当最大流为N的时候，就可以构造这么一个回路
接着费用就比较简单了，因为费用在每个边上，所以当两点之间存在边的时候，构造边
边的容量是1，费用是题目所给，别忘了给反向边
#include<cstdio>
#include<cstring>
#include<queue>
#define min(a,b) a>b?b:a
using namespace std;
const int MAX = 110;
const int INF = 0x7fffffff;
int N, M, K;
int SS, TT;
int mm[2 * MAX][2 * MAX]; //flow map
int cc[2 * MAX][2 * MAX]; //cost map
int prev[2 * MAX];//下面4个是必须要的
int flow[2 * MAX];
int dis[2 * MAX];
int in[2 * MAX];
int map[110][110];
//主要对这两个函数进行修改
void ready()
{
memset(map,0,sizeof(map));
for(int i=1;i<=M;i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
if(map[x][y]==0) map[x][y]=c;
else map[x][y]=min(map[x][y],c);
}
}
void makeMap()
{
SS = 0, TT = N + N + 1;
memset(mm, 0, sizeof(mm));
for(int i = 1; i <= N; i++)
mm[SS][i] = 1;//限制入度和出度，想想题目的限制
for(int i = 1+N; i <= N+N; i++)
mm[i][TT] = 1;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
if(map[i][j]!=0)
mm[i][j + N] = 1;
//make the cost map
memset(cc, 0, sizeof(cc));
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
if(map[i][j])
{
cc[i][j + N] = map[i][j];
cc[j + N][i] = -map[i][j];
//构造费用流的负权边
}
}
int spfa()
{
memset(in, 0, sizeof(in));
memset(dis, -1, sizeof(dis));
memset(prev, -1, sizeof(prev));
memset(flow, 0, sizeof(flow));
in[SS] = 1, dis[SS] = 0, flow[SS] = INF;
queue<int> q;
q.push(SS);
while(!q.empty())
{
int u = q.front();
q.pop();
in[u] = 0;
for(int j = SS; j <= TT; j++)
{
if(mm[u][j] > 0 && (dis[j] == -1 || dis[u] + cc[u][j] < dis[j]))
{
dis[j] = dis[u] + cc[u][j];
//in[j] = 1;
prev[j] = u;
flow[j] = min(flow[u], mm[u][j]);
if(in[j] == 0) in[j] = 1, q.push(j);
}
}
}
return flow[TT];
}
int mcmf()
{
int res = 0,flow=0;
while(1)
{
int now = spfa();
if(now == 0) break;
int u = TT;
flow+=now;
while(u != SS)
{
int v = prev[u];
mm[v][u] -= now;
mm[u][v] += now;
res += now * cc[v][u];
u = v;
}
}
//printf("flow=%d/n",flow);
if(flow==N) return res;
else return -1;
}
int main()
{
while(scanf("%d%d", &N, &M)!=EOF)
{
ready();
makeMap();
int t=mcmf();
printf("%d/n", t);
}
return 0;
}