HDU 1853 Cyclic Tour//料金フロー
5570 ワード
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).
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
Sample Output
Author
RoBa@TJU
Source
HDU 2007 Programming Contest - Final
Recommend
lcy
本当に最初はこの問題が費用の流れでできるとは思わなかった...
それから大牛の問題解を見てやっと思いついた.
いくつかの重要な条件
1.各ポイントは1つのループにのみ属し、すべてのポイントがループに属している必要があります.
2.回路ごとに2つ以上の点が必要
3.回路総費用が最小なら
これらの条件はこの問題の解法を制限している.
KMでいいです.KMアルゴリズムをもっと熟知させるために、明日KMの解題報告をします.
最小費用フローの構図方法について話しましょう
まず、2つのスーパーソースポイントS、Tを設立します.
Sは各点に辺を結んで、容量は1で、費用は0で、制限するのは各点の入度です
TはI+Nごとに接続され,容量は1,費用は0であり,各点の出度に制限される.
これにより,最大流がNである場合に,このような回路を構築できるという第1の条件が満たされる.
次に費用は比較的簡単で、費用は各辺にあるので、2点の間に辺が存在する場合、辺を構築します.
辺の容量は1で、費用はテーマがあげたので、反対側にあげるのを忘れないでください.
#include
#include
#include
#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 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;
}
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).
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
Source
HDU 2007 Programming Contest - Final
Recommend
lcy
本当に最初はこの問題が費用の流れでできるとは思わなかった...
それから大牛の問題解を見てやっと思いついた.
いくつかの重要な条件
1.各ポイントは1つのループにのみ属し、すべてのポイントがループに属している必要があります.
2.回路ごとに2つ以上の点が必要
3.回路総費用が最小なら
これらの条件はこの問題の解法を制限している.
KMでいいです.KMアルゴリズムをもっと熟知させるために、明日KMの解題報告をします.
最小費用フローの構図方法について話しましょう
まず、2つのスーパーソースポイントS、Tを設立します.
Sは各点に辺を結んで、容量は1で、費用は0で、制限するのは各点の入度です
TはI+Nごとに接続され,容量は1,費用は0であり,各点の出度に制限される.
これにより,最大流がNである場合に,このような回路を構築できるという第1の条件が満たされる.
次に費用は比較的簡単で、費用は各辺にあるので、2点の間に辺が存在する場合、辺を構築します.
辺の容量は1で、費用はテーマがあげたので、反対側にあげるのを忘れないでください.
#include
#include
#include
#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
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;
}