无向图费用流
还有一段话摘自别人博客
这道题是无向图的最小费用最大流问题，看清楚是无向图的。这么说无向图和有向图的费用流问题有什么区别呢？主要是反向边的问题。首先我们说一下最大流问题中的反向边，我们需要将其cap[u][v]=0表示容量为0，而在费用流问题中添加了费用，所以肯定不能像之前那么简单处理了，那怎么办呢？在有向图中，没有存在的反向边我们用cap[u][v]=0表示容量为0，cost[v][u]=-cost[u][v]表示取反的费用，简单说就是讲这部分费用减除，相当于没有走。 现在可以说一下无向图和有向图的不同了，既然两个方向都是可以走的，那么我们就将原本有的一条边变化出了四条边，两个原有边，两个反向边，原有两个边相互独立，不能将这两个原有边看成互为反向边，否则就出现了环路，spfa就走不通
#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);} const LL INF = 100000000; #define MAXN 110 struct node { int u,v,next; LL cap,flow,cost; }edge[5005 * 4]; int N,M,cnt,src,tag; LL K,D,F,C,d[5005]; struct point { LL x,y,w; }res[5005]; bool inq[MAXN]; int head[MAXN],p[MAXN]; void add(int u, int v, LL cost, LL 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++; } void read() { for (int i = 1; i <= M; i++) scanf("%lld%lld%lld",&res[i].x,&res[i].y,&res[i].w); scanf("%lld%lld",&D,&K); cnt = 0; src = 0; tag = N; memset(head,-1,sizeof(head)); for (int i = 1; i <= M; i++) { add(res[i].x,res[i].y,res[i].w,K); add(res[i].y,res[i].x,res[i].w,K); } add(0,1,0,D); } bool SPFA() { queue<int>q; while (!q.empty()) q.pop(); for (int i = 0; i < MAXN; i++) d[i] = INF; d[src] = 0; memset(p,-1,sizeof(p)); memset(inq,false,sizeof(inq)); q.push(src); inq[src] = true; 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]) { inq[v] = true; q.push(v); } } } } //printf("%lld ",d[tag]); return d[tag] != INF; } void slove() { F = C = 0; while (SPFA()) { LL a = INF; for (int i = p[tag]; i != -1; i = p[edge[i].u]) a = min(a,edge[i].cap - edge[i].flow); for (int i = p[tag]; i != -1; i = p[edge[i].u]) { edge[i].flow += a; edge[i ^ 1].flow -= a; } F += a; C += d[tag] * a; } } int main() { //freopen("sample.txt","r",stdin); while (scanf("%d%d",&N,&M) != EOF) { read(); slove(); if (F == D) printf("%lld ",C); else puts("Impossible."); } return 0; }