无源汇有上下界网络的可行流
4 评论45次阅读2008.04.01 22:40; 作者：Felicia
最近学习使用LaTeX写文章，碰巧今天学习了容量有上下界网络流问题，就写了一个简要总结。
在这里下载pdf文档。
练习题：ZJU2314
下面是我的代码
下载: zju2314.cpp
/*****************************************************************
Author: WHU_GCC
Created Time: 2008/3/31 21:05:10
File Name: zju2314.cpp
Description:
*****************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
struct ee {
int s, t;
ee(int _s, int _t):s(_s),t(_t){}
};
vector <ee> ptr;
vector <int> cap;
vector <int> lb;
class Graph {
public:
struct edge {
int to, cap, back;
edge(int t,int c,int b):to(t),cap(c),back(b){}
};
inline void getmin(int &a,const int b){if (b<a) a=b;}
std::vector<std::vector<edge> > adj;
int n;
Graph(int n) : n(n) {
adj.resize(n);
int i;
for (i=0; i<n; i++)
adj[i].clear();
}
void Insert(int i, int j, int c, int flag) {
adj[i].push_back(edge(j, c, adj[j].size()));
adj[j].push_back(edge(i, 0, adj[i].size()-1));
if (flag) {
ptr.push_back(ee(i, adj[i].size() - 1));
}
}
void Insert2(int i, int j, int c) {
adj[i].push_back(edge(j, c, adj[j].size()));
adj[j].push_back(edge(i, c, adj[i].size()-1));
}
int Dinic(int s, int t) {
int *q=new int[n], *prev=new int[n];
int allflow=0, u, v, i, z;
while (true) {
for (i=0; i<n; i++) prev[i]=-1;
int qf=0, qb=0;
prev[q[qb++]=s] = -2;
while (qb>qf && prev[t]==-1)
for (u=q[qf++], i=0, v; i<adj[u].size(); i++)
if (prev[v=adj[u][i].to]==-1 && adj[u][i].cap>0)
prev[q[qb++]=v] = adj[u][i].back;
if (prev[t] == -1) break;
for (i=0; i<adj[t].size(); i++)
if (adj [z=adj[t][i].to] [adj[t][i].back].cap>0 && prev[z]!=-1) {
int flow = adj[z][adj[t][i].back].cap;
for (v=z, u=prev[v]; u>=0; v=adj[v][u].to, u=prev[v])
getmin(flow, adj[adj[v][u].to][adj[v][u].back].cap);
if (!flow) continue;
adj[z][adj[t][i].back].cap -= flow;
adj[t][i].cap += flow;
for (v=z, u=prev[v]; u>=0; v=adj[v][u].to, u=prev[v]) {
adj[adj[v][u].to][adj[v][u].back].cap -= flow;
adj[v][u].cap += flow;
}
allflow += flow;
}
}
return allflow;
}
};
int main() {
int n, m;
int ca;
for (scanf("%d", &ca); ca--;) {
scanf("%d%d", &n, &m);
Graph g(n + 2);
ptr.clear();
cap.clear();
lb.clear();
int ou = 0;
for (int i = 0; i < m; i++) {
int t1, t2, tc, tb;
scanf("%d%d%d%d", &t1, &t2, &tb, &tc);
g.Insert(t1, t2, tc - tb, 1);
cap.push_back(tc - tb);
lb.push_back(tb);
ou += tb;
g.Insert(0, t2, tb, 0);
g.Insert(t1, n + 1, tb, 0);
}
int ans = g.Dinic(0, n + 1);
if (ans != ou)
printf("NOn");
else {
printf("YESn");
for (int i = 0; i < ptr.size(); i++)
printf("%dn", cap[i] - g.adj[ptr[i].s][ptr[i].t].cap + lb[i]);
}
printf("n");
}
return 0;
}
Author: WHU_GCC
Created Time: 2008/3/31 21:05:10
File Name: zju2314.cpp
Description:
*****************************************************************/
#include <iostream>
#include <vector>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
struct ee {
int s, t;
ee(int _s, int _t):s(_s),t(_t){}
};
vector <ee> ptr;
vector <int> cap;
vector <int> lb;
class Graph {
public:
struct edge {
int to, cap, back;
edge(int t,int c,int b):to(t),cap(c),back(b){}
};
inline void getmin(int &a,const int b){if (b<a) a=b;}
std::vector<std::vector<edge> > adj;
int n;
Graph(int n) : n(n) {
adj.resize(n);
int i;
for (i=0; i<n; i++)
adj[i].clear();
}
void Insert(int i, int j, int c, int flag) {
adj[i].push_back(edge(j, c, adj[j].size()));
adj[j].push_back(edge(i, 0, adj[i].size()-1));
if (flag) {
ptr.push_back(ee(i, adj[i].size() - 1));
}
}
void Insert2(int i, int j, int c) {
adj[i].push_back(edge(j, c, adj[j].size()));
adj[j].push_back(edge(i, c, adj[i].size()-1));
}
int Dinic(int s, int t) {
int *q=new int[n], *prev=new int[n];
int allflow=0, u, v, i, z;
while (true) {
for (i=0; i<n; i++) prev[i]=-1;
int qf=0, qb=0;
prev[q[qb++]=s] = -2;
while (qb>qf && prev[t]==-1)
for (u=q[qf++], i=0, v; i<adj[u].size(); i++)
if (prev[v=adj[u][i].to]==-1 && adj[u][i].cap>0)
prev[q[qb++]=v] = adj[u][i].back;
if (prev[t] == -1) break;
for (i=0; i<adj[t].size(); i++)
if (adj [z=adj[t][i].to] [adj[t][i].back].cap>0 && prev[z]!=-1) {
int flow = adj[z][adj[t][i].back].cap;
for (v=z, u=prev[v]; u>=0; v=adj[v][u].to, u=prev[v])
getmin(flow, adj[adj[v][u].to][adj[v][u].back].cap);
if (!flow) continue;
adj[z][adj[t][i].back].cap -= flow;
adj[t][i].cap += flow;
for (v=z, u=prev[v]; u>=0; v=adj[v][u].to, u=prev[v]) {
adj[adj[v][u].to][adj[v][u].back].cap -= flow;
adj[v][u].cap += flow;
}
allflow += flow;
}
}
return allflow;
}
};
int main() {
int n, m;
int ca;
for (scanf("%d", &ca); ca--;) {
scanf("%d%d", &n, &m);
Graph g(n + 2);
ptr.clear();
cap.clear();
lb.clear();
int ou = 0;
for (int i = 0; i < m; i++) {
int t1, t2, tc, tb;
scanf("%d%d%d%d", &t1, &t2, &tb, &tc);
g.Insert(t1, t2, tc - tb, 1);
cap.push_back(tc - tb);
lb.push_back(tb);
ou += tb;
g.Insert(0, t2, tb, 0);
g.Insert(t1, n + 1, tb, 0);
}
int ans = g.Dinic(0, n + 1);
if (ans != ou)
printf("NOn");
else {
printf("YESn");
for (int i = 0; i < ptr.size(); i++)
printf("%dn", cap[i] - g.adj[ptr[i].s][ptr[i].t].cap + lb[i]);
}
printf("n");
}
return 0;
}
发表回复
Rainco | 1F
四月 4th, 2008 at 02:16
很经典的问题了…….
Felicia | 2F
四月 4th, 2008 at 10:40
我知道这是很经典的问题。以前一直没仔细想，直到最近才仔细想明白，所以整理了一下思路放在这里。大牛不要见笑。
l-y-p | 3F
四月 8th, 2008 at 17:51
大牛多写几篇图论与搜索的日志啊！向大牛学习了……
xiaoze | 4F
四月 11th, 2008 at 16:17
你好，看了你的PDF分析，我在网上找了周源的那篇文章，没找到，不知道你那里是否有，请发我邮箱谢谢！