| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
大家帮个忙!#include <iostream>
#include<vector>
#include <algorithm>
#include <queue>
#define MAX 450
#define INF 1000000000
using namespace std;
vector<int> v[MAX];//图的领接表
int prev[MAX];
int mark[MAX];
int cap[MAX][MAX];
bool augmentable(int s, int t)
{
queue<int> q;
memset(prev, -1, sizeof(prev));
memset(mark, 0, sizeof(mark));
prev[s] = s;
q.push(s);
mark[s]=1;
while (!q.empty())
{
int p = q.front(), i;
q.pop();
for (i = 0; i < v[p].size(); i++)
{
int tt=v[p][i];
if (cap[p][tt] > 0 && mark[tt]==0)
{
prev[tt] = p;
mark[tt]=1;
if (tt == t) return true;
else q.push(tt);
}
}
}
return false;
}
int maxFlow(int s, int t) {
int flow = 0, i;
while (augmentable(s, t)) {
int extend = INF;
for (i = t; i != s; i = prev[i]) if(extend > cap[prev[i]][i]) extend = cap[prev[i]][i];
for (i = t; i != s; i = prev[i]) {
cap[prev[i]][i] -= extend;
cap[i][prev[i]] += extend;
}
flow += extend;
}
return flow;
}
这么求最大流怎么错了??小弟我初学网络流,还望指教哈!!
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator