首页 > 代码库 > Farm Tour
Farm Tour
题目描述
To show off his farm in the best way, he walks a tour that starts at his house, potentially travels through some fields, and ends at the barn. Later, he returns (potentially through some fields) back to his house again.
He wants his tour to be as short as possible, however he doesn‘t want to walk on any given path more than once. Calculate the shortest tour possible. FJ is sure that some tour exists for any given farm.
输入
* Lines 2..M+1: Three space-separated integers that define a path: The starting field, the end field, and the path‘s length.
输出
样例输入
4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2
样例输出
6
最小费用最大流模板
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct data{
int to,cap,cost,next;
}g[80001];
int h[1101],d[1101],k=1,used[1101],que[100000],head,tail,last[1101],ans=0;
int INF;
void add(int from,int to,int cap,int cost)
{
g[++k].next=h[from];h[from]=k;g[k].to=to;g[k].cap=cap;g[k].cost=cost;
g[++k].next=h[to];h[to]=k;g[k].to=from;g[k].cap=0;g[k].cost=-cost;
}
bool spfa(int s,int t)
{
memset(last,0,sizeof(last));
memset(d,127/3,sizeof(d));INF=d[0];
memset(used,0,sizeof(used));
head=tail=50000;que[tail++]=s;used[s]=1;d[s]=0;
while(head<=tail)
{
int u=que[head++];
for(int i=h[u];i;i=g[i].next)
{
if(g[i].cap&&d[u]+g[i].cost<d[g[i].to])
{
d[g[i].to]=d[u]+g[i].cost;last[g[i].to]=i;
if(!used[g[i].to])
{
if(d[g[i].to]<d[que[head]])que[--head]=g[i].to;
else que[tail++]=g[i].to;used[g[i].to]=1;
}
}
}
used[u]=0;
}
if(d[t]==INF)return false;
return true;
}
void mcf(int t)
{
int minn=INF;
for(int i=last[t];i;i=last[g[i^1].to])minn=min(minn,g[i].cap);
for(int i=last[t];i;i=last[g[i^1].to])
{
ans+=g[i].cost*minn;
g[i].cap-=minn;g[i^1].cap+=minn;
}
}
int main()
{
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y,z;scanf("%d%d%d",&x,&y,&z);
add(x,y,1,z);add(y,x,1,z);
}
add(n+1,1,2,0);add(n,n+2,2,0);
while(spfa(n+1,n+2))mcf(n+2);
printf("%d",ans);
return 0;
}
Farm Tour