首页 > 代码库 > poj3422 来一道费用流
poj3422 来一道费用流
题目链接
poj3422
真是感觉网络流越来越神奇了。
1、最小费用流 -- 最大费用流之间转化
2、拆点
3、费用 OR 流量 (cost, flow)
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> using namespace std; #define clr(x) memset(x,0,sizeof(x)) #define fp1 freopen("in.txt","r",stdin) #define fp2 freopen("out.txt","w",stdout) #define pb push_back #define INF 0x3c3c3c3c typedef long long LL; //网络中可以有负权边,但不能有负权圈。 //每次先调用init(); 初始maxn、INF之类。 //Addedge(cap, flow):cap是容量,flow是流量。 const int maxn = 100000; struct Edge { int from, to, cap, flow, cost; }; struct MCMF { int n, m, s, t; vector<Edge> edges; vector<int> G[maxn]; int inq[maxn]; //是否在队列中 int d[maxn]; //Bellman-Ford int p[maxn]; //上一条弧 int a[maxn]; //可改进量 void init(int n) //感觉每次调用都要调用init初始化哪 { this->n = n; for(int i = 0;i < n;i++) G[i].clear(); edges.clear(); //clr(p); clr(a); clr(d); } void addedge(int from, int to, int cost, int cap) { edges.pb((Edge){from, to, cap, 0, cost}); edges.pb((Edge){to, from, 0, 0, -cost}); m = edges.size(); G[from].pb(m-2); G[to].pb(m-1); } //其他成员函数 bool spfa(int s, int t, int &flow, int &cost) { for(int i = 0;i < n;i++) d[i] = INF; clr(inq); d[s] = 0; inq[s] = 1; p[s] = 0; a[s] = INF; queue<int> Q; Q.push(s); while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0;i < G[u].size();i++){ Edge &e = edges[G[u][i]]; if(e.cap>e.flow && d[e.to]>d[u]+e.cost){ d[e.to] = d[u] + e.cost; p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap-e.flow); if(!inq[e.to]){ Q.push(e.to); inq[e.to] = 1; } } } } if(d[t] == INF) return false; //s-t不连通,失败退出 flow += a[t]; cost += d[t]*a[t]; int u = t; while(u != s){ edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; u = edges[p[u]].from; } return true; } int Mincost(int s, int t) { int flow = 0, cost = 0; while(spfa(s, t, flow, cost)); return cost; } }; MCMF flow; int map1[55][55]; int main() { //freopen("in.txt", "r", stdin); int n, m; while (scanf("%d %d", &n, &m) == 2) { flow.init(n*n*2+100); int i, j; for (int i=1; i <= n;i++) { for (int j=1; j <= n;j++) { scanf("%d", &map1[i][j]); } } for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { int u = (i - 1) * n + j; flow.addedge(u, n*n+u, -map1[i][j], 1); //reversed flow.addedge(u, n*n+u, 0, m-1); if(j != n){ flow.addedge(u, u+1, 0, m); flow.addedge(n*n+u, u+1, 0, m); } if(i != n){ flow.addedge(u, u+n, 0, m); flow.addedge(n*n+u, u+n, 0, m); } } } flow.addedge(0, 1, 0, m); //SuperSource flow.addedge(n*n*2, n * n * 2 + 1, 0, m); //SuperSink cout<<-flow.Mincost(0, n*n*2+1); } return 0; }
poj3422 来一道费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。