题意是从1到n 在回到1 每条边用一次 可以的话输出最短路
最小费用最大流 费用是最短路 此外取点0 和 n+1 , 0 - 1 费用0 cap = 2 n-n+1 也是这样 其他每条边用的次数是1
最大流等于2 说明可行
无向图 第一次学了拆边
一条无向边对应2条有向的 每条还有一条相反的 cap = 0 cost = -w的反向边 总共4条
要用邻接表存储
邻接矩阵不支持平行边 和 反向边
网络流拆点 和 拆边 是很多的 第一次遇到 似懂非懂的
#include#include #include using namespace std; const int MAX = 110; int n,m; struct edge { int u; int v; int cost; int flow; int cap; int next; }e[50000]; int dis[MAX]; int first[MAX]; int p[MAX]; bool vis[MAX]; int edgenum; int f,c; void add(int u,int v,int w,int num) { e[edgenum].u = u; e[edgenum].v = v; e[edgenum].cap = num; e[edgenum].cost = w; e[edgenum].flow = 0; e[edgenum].next = first[u]; first[u] = edgenum++; e[edgenum].u = v; e[edgenum].v = u; e[edgenum].cap = 0; e[edgenum].cost = -w; e[edgenum].flow = 0; e[edgenum].next = first[v]; first[v] = edgenum++; } void EK() { queue q; c = f = 0; while(1) { for(int i = 0;i <= n+1; i++) dis[i] = (i == 0 0 : 999999999); memset(vis,false,sizeof(vis)); memset(p,-1,sizeof(p)); q.push(0); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = false; for(int k = first[u]; k != -1; k = e[k].next) { int v = e[k].v; if(e[k].cap > e[k].flow && dis[v] > dis[u] + e[k].cost) { dis[v] = dis[u] + e[k].cost; p[v] = k; if(!vis[v]) { vis[v] = true; q.push(v); } } } } if(dis[n+1] == 999999999) break; int a = 999999999; for(int u = p[n+1]; u != -1; u = p[e[u].u]) a = min(a,e[u].cap - e[u].flow); for(int u = p[n+1]; u != -1; u = p[e[u].u]) { e[u].flow += a; e[u^1].flow -= a; } c += dis[n+1] * a; f += a; } } int main() { int i,j; int s,e,w; while(scanf("%d",&n),n) { scanf("%d",&m); edgenum = 0; memset(first,-1,sizeof(first)); add(0,1,0,2); add(n,n+1,0,2); for(i = 0;i < m; i++) { scanf("%d %d %d",&s,&e,&w); add(s,e,w,1); add(e,s,w,1); } EK(); if(f == 2) printf("%d\n",c); else printf("Back to jail\n"); } return 0; }