题意：
给n个点，m条边，有np个源点，nc个汇点，求最大流
思路：
超级源点把全部源点连起来。边权是该源点的最大同意值；
全部汇点和超级汇点连接起来，边权是该汇点的最大同意值。
跑最大流
code：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<set>
#include<cmath>
#include<cstdlib>
using namespace std; #define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a)) typedef pair<int,int> pii;
typedef long long LL;
//------------------------------
const int maxn = 205;
const int maxm = 205 * 205;
const int max_nodes = maxn; struct Edge{
int from, to;
int capacity, flow;
Edge(){}
Edge(int from_, int to_, int capacity_, int flow_){
from = from_;
to = to_;
capacity = capacity_;
flow = flow_;
}
};
Edge edges[maxm];
int cnte;
vector<int> g[maxn];
void graph_init(){
cnte = 0;
for(int i = 0; i < maxn; i++) g[i].clear();
} void add_Edge(int from, int to, int cap){
edges[cnte].from = from;
edges[cnte].to = to;
edges[cnte].capacity = cap;
edges[cnte].flow = 0;
g[from].push_back(cnte);
cnte++;
edges[cnte].from = to;
edges[cnte].to = from;
edges[cnte].capacity = 0;
edges[cnte].flow = 0;
g[to].push_back(cnte);
cnte++;
} int source; // 源点
int sink; // 汇点
int p[maxn]; // 可增广路上的上一条弧的编号
int num[maxn]; // 和 t 的最短距离等于 i 的节点数量
int cur[maxn]; // 当前弧下标
int d[maxn]; // 残量网络中节点 i 到汇点 t 的最短距离
bool visited[maxn];
int num_nodes, num_edges; void bfs(){ // 预处理, 反向 BFS 构造 d 数组
memset(visited, 0, sizeof(visited));
queue<int> q;
q.push(sink);
visited[sink] = true;
d[sink] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = 0; i < g[u].size(); i++){
Edge& e = edges[g[u][i] ^ 1];
int v = e.from;
if(!visited[v] && e.capacity > e.flow){
visited[v] = true;
d[v] = d[u] + 1;
q.push(v);
}
}
}
}
int augment(){ // 增广
int u = sink, df = INF;
// 从汇点到源点通过 p 追踪增广路径, df 为一路上最小的残量
while(u != source){
Edge& e = edges[p[u]];
df = min(df, e.capacity - e.flow);
u = e.from;
}
u = sink;
// 从汇点到源点更新流量
while(u != source){
Edge& e = edges[p[u]];
e.flow += df;
edges[p[u]^1].flow -= df;
u = e.from;
}
return df;
}
int max_flow(){
int flow = 0;
bfs();
memset(num, 0, sizeof(num));
for(int i = 0; i < num_nodes; i++) num[d[i]] ++; // 这个地方，针对的是点从0開始编号的情况
int u = source;
memset(cur, 0, sizeof(cur));
while(d[source] < num_nodes){
if(u == sink){
flow += augment();
u = source;
}
bool advanced = false;
for(int i = cur[u]; i < g[u].size(); i++){
Edge& e = edges[g[u][i]];
if(e.capacity > e.flow && d[u] == d[e.to] + 1){
advanced = true;
p[e.to] = g[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if(!advanced){ //retreat
int m = num_nodes - 1;
for(int i = 0; i < g[u].size(); i++){
Edge& e = edges[g[u][i]];
if(e.capacity > e.flow) m = min(m, d[e.to]);
}
if(--num[d[u]] == 0) break; // gap 优化
num[d[u] = m+1] ++;
cur[u] = 0;
if(u != source){
u = edges[p[u]].from;
}
}
}
return flow;
}
//------------------------我是分界线，上面是模板--------------------------
int np, nc, n, m; void solve(){
graph_init();
int u, v, w;
char ch;
for(int i = 1; i <= m; i++){
while(scanf("%c", &ch)){
if(ch == '(') break;
}
scanf("%d,%d%c%d",&u,&v,&ch,&w);
add_Edge(u, v, w);
}
for(int i = 1; i <= np; i++){
while(scanf("%c", &ch)){
if(ch == '(') break;
}
scanf("%d%c%d",&u, &ch, &w);
add_Edge(n, u, w);
}
for(int i = 1; i <= nc; i++){
while(scanf("%c", &ch)){
if(ch == '(') break;
}
scanf("%d%c%d",&v, &ch, &w);
add_Edge(v, n+1, w);
} num_nodes = n+2;
source = n; sink = n+1; int ans = max_flow();
printf("%d\n",ans);
}
int main(){
while(scanf("%d%d%d%d",&n,&np, &nc, &m) != EOF){
solve();
}
return 0;
}
最终自己写了一个还不错的最大流啦....窝原来用的那个模板我囧的非常好了啊！
可是我干囧大家好像都再说Dinic是好。又有人在说ISAP好像更棒啊！
最终我如今两个都敲一下就好啦~~
ISAP跟DINIC还是有非常多相似的。
。