Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

大家帮个忙!

Posted by scuxy at 2008-04-16 13:38:50
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator