费用流第一题主要是临街表实现这个算法的问题。这里存下
思路还是比较简单。源点0，汇点N+1.费用为边长。容量为1.（普通边）。添加边为2（0-1 N-N+1）
代码
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <stack> #include <queue> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <climits> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define LL long long #define PI 3.1415926535897932626 using namespace std; int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);} #define MAXN 110 const int INF = 0x3f3f3f3f ; struct node { int u,v,next; int flow,cost; int cap; }edge[20100]; int head[MAXN],d[MAXN]; bool inq[MAXN]; int p[MAXN],cnt; int c,ans,N,M; void add(int u, int v, int cost, int cap) { edge[cnt].v = v; edge[cnt].u = u; edge[cnt].cost = cost; edge[cnt].cap = cap; edge[cnt].flow = 0; edge[cnt].next = head[u]; head[u] = cnt++; // 反向边 edge[cnt].v = u; edge[cnt].u = v; edge[cnt].cost = -cost; edge[cnt].cap = 0; edge[cnt].flow = 0; edge[cnt].next = head[v]; head[v] = cnt++; } bool spfa(int s,int t) { queue<int>q; while (!q.empty()) q.pop(); q.push(s); memset(inq,false,sizeof(inq)); inq[s] = true; memset(d,0x3f,sizeof(d)); d[0] = 0; memset(p,-1,sizeof(p)); while (!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if (edge[i].cap > edge[i].flow && d[v] > d[u] + edge[i].cost) { d[v] = d[u] + edge[i].cost; p[v] = i; if (!inq[v]) { q.push(v); inq[v] = true; } } } } return d[N + 1] != INF; } void slove(int s,int t) { c = 0 ,ans = 0; while (spfa(s,t)) { int a = INF; for (int i = p[N + 1]; i != -1; i = p[edge[i].u]) a = min(a,edge[i].cap - edge[i].flow); for (int i = p[N + 1]; i != -1; i = p[edge[i].u]) { edge[i].flow += a; edge[i ^ 1].flow -= a; } c += d[N + 1] * a; ans += a; } } int main() { //freopen("sample.txt","r",stdin); while (scanf("%d",&N)!=EOF) { if (N == 0) break; memset(head,-1,sizeof(head)); cnt = 0; scanf("%d",&M); while(M--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w,1); add(v,u,w,1); } add(0,1,0,2); add(N,N + 1,0,2); slove(0,N + 1); if (ans >= 2) printf("%d ",c); else puts("Back to jail"); } return 0; }