最小费用最大流。
求1到n再到1的最小费用。
转换成以一个源点到1点容量为2，n到汇点容量为2的图。因为路是双向的，所以可以转换为从1点发出两条路到达n点。
中间路的容量都为1满足只走一次。
邻接矩阵WA了，因为建图的时候，每条边需要建两次。。。= =。。。
刚才很不情愿得改成邻接表了。。。不过写着很顺利。。。基本没咋改就A了。。。
#include <cstdio> #include <cstdlib> #include <iostream> #include <string.h> #include <queue> #include <limits.h> #define MAX 1010 using namespace std; int n,m,cou; typedef struct NODE{ int to,cap,cost,from; int next; }NODE; NODE node[MAX*MAX]; int tour[MAX]; void init() { cou = 2; memset(node,'/0',sizeof(node)); memset(tour,0,sizeof(tour)); } int flow[MAX][MAX]; queue <int> Q; int MincostMaxflow(int s,int t) { int a,c,cap,i,cost,dis[MAX]; int pre[MAX],re[MAX],u,v; int inq[MAX]; int ind; c = 0; memset(flow,0,sizeof(flow)); while(1) { for(i=s; i<=t; i++) dis[i] = INT_MAX; dis[s] = 0; memset(inq,0,sizeof(inq)); Q.push(s); inq[s] = 1; pre[s] = s; while( !Q.empty() ) { u = Q.front(); Q.pop(); inq[u] = 0; ind = tour[u]; while( ind != 0 ) { cap = node[ind].cap; u = node[ind].from; v = node[ind].to; cost = node[ind].cost; if( cap > 0 && dis[v] > dis[u] + cost ) { dis[v] = dis[u] + cost; pre[v] = u; re[v] = ind; if( !inq[v] ) { Q.push(v); inq[v] = 1; } } ind = node[ind].next; } } if( dis[t] == INT_MAX ) break; a = INT_MAX; for(u=t; u!=s; u=pre[u]) if( node[re[u]].cap < a ) a = node[re[u]].cap; for(u=t; u!=s; u=pre[u]) { node[re[u]^1].cap += a; node[re[u]].cap -= a; } c += dis[t]*a; } return c; } void Add(int u,int v,int cap,int cost) { node[cou].from = u; node[cou].to = v; node[cou].cap = cap; node[cou].cost = cost; node[cou].next = tour[u]; tour[u] = cou++; node[cou].from = v; node[cou].to = u; node[cou].cap = 0; node[cou].cost = -cost; node[cou].next = tour[v]; tour[v] = cou++; } int main() { int from,to,len,ans; while( ~scanf("%d%d",&n,&m) ) { init(); while( m-- ) { scanf("%d%d%d",&from,&to,&len); Add(from,to,1,len); Add(to,from,1,len); } Add(0,1,2,0); Add(n,n+1,2,0); ans = MincostMaxflow(0,n+1); printf("%d/n",ans); } return 0; }
