也是一道模板题目...敲一遍熟悉熟悉
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <climits>//形如INT_MAX一类的
#define MAX 205
#define INF 0x7FFFFFFF
# define eps 1e-5
//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂
using namespace std;
int cap[MAX][MAX],pre[MAX],flow[MAX];
int m,n;
int bfs(int s,int e)
{
queue<int >q;
memset(pre,-1,sizeof(pre));
pre[s] = 0;
flow[s] = INF;
q.push(s);
while(! q.empty())
{
int t = q.front();
q.pop();
if(t == e)
break;
for(int i=1; i<=m; i++)
{
if(pre[i] == -1 && cap[t][i] > 0 )
{
q.push(i);
pre[i] = t;
flow[i] = min(flow[t],cap[t][i]);
}
}
}
if(pre[e] == -1)
return -1;
return flow[e];
}
int maxflow(int s,int e)
{
int imp=0;
int sum=0;
while((imp = bfs(s,e)) != -1)
{
int ind = e;
while(ind != s)
{
cap[pre[ind]][ind] -= imp;
cap[ind][pre[ind]] += imp;
ind = pre[ind];
}
sum += imp;
}
return sum;
}
void init()
{
memset(cap,0,sizeof(cap));
memset(flow,0,sizeof(flow));
}
int main()
{
int a,b,c;
while(scanf("%d%d",&n,&m) != EOF)
{
init();
for(int i=0; i<n; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a == b)
continue;
cap[a][b] += c;
}
printf("%d\n",maxflow(1,m));
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj分类poj分类poj分类poj分类
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ2002-Squares 解题报告+AC代码
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码
Poj中一些题目的源代码,里面共有二十多道题目,OI
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码