先把多源多汇网络转化为单源单汇网络,然后EK模版
code
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 102;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
int n,np,nc,m;
int cap[maxn][maxn],pre[maxn];
bool vis[maxn];
bool bfs(int s,int t){
int p;
queue<int> q;
SET(pre,-1);SET(vis,false);
pre[s]=-1;
q.push(s);
while(!q.empty()){
p=q.front();q.pop();
if(p==n+1) return true;
FOR(i,0,t){
if(cap[p][i] && !vis[i]){
pre[i]=p;
vis[i]=true;
q.push(i);
}
}
}
return false;
}
int EK(int s,int t){
int flow=0,d;
while(bfs(s,t)){
d=INF;
for(int i=t;i!=s;i=pre[i])
d=min(cap[pre[i]][i],d);
for(int i=t;i!=s;i=pre[i]){
cap[pre[i]][i]-=d;
cap[i][pre[i]]+=d;
}
flow+=d;
}
return flow;
}
int main()
{
int a,b,z;
while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){
SET(cap,0);
FOR(i,1,m){
scanf(" (%d,%d)%d",&a,&b,&z);
cap[a+1][b+1]=z;
}
FOR(i,1,np){
scanf(" (%d)%d",&a,&z);
cap[0][a+1]=z;
}
FOR(i,1,nc){
scanf(" (%d)%d",&a,&z);
cap[a+1][n+1]=z;
}
PD(EK(0,n+1));LN;
}
return 0;
}
分享到:
相关推荐
poj 1459 Power Network.md
北大POJ1459-Power Network 解题报告+AC代码
北大POJ2531-Network Saboteur 解题报告+AC代码
北大POJ2109-Power of Cryptography 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1001-Precision power 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
利用并查集判断环路,以及快速排序计算最小生成树
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ1048,加强版的约瑟夫问题 难度中等