我用ｂｆｓ写的增广路径，重边也考虑了，　数组开２１０也够大，但是交上去是ＲＥ
我怀疑是数组开小了，　于是开了个５００的，就变ＴＬＥ了．不知道是怎么一回事，请大牛赐教．
附代码：
#include <iostream>
#include <queue>

using namespace std;
#include "memory.h"
#define MAX 210
int cap[MAX][MAX], f[MAX][MAX], path[MAX], cf[MAX][MAX];／／ｆ流值，ｃｆ残留网络，ｃａｐ容量
int len, n, m;
bool u[MAX];／／是否访问过的标记
int bfs(int from)
{
	int min = 99999999, i;
	std::queue<int> q;
	q.push(from);
	u[0] = true;

	while(!q.empty())
	{
		int next = q.front();
		q.pop();
		
		if(next == n - 1) 
		{
			for(i = n - 1; path[i] != -1; i = path[i])
			{
				min = min > cf[path[i]][i] ? cf[path[i]][i]:min;
			}
			return min;
		}
		for(i = 1; i <= n - 1; i++)
		{
			if(!u[i] && cf[next][i] > 0)
			{
				q.push(i);
				u[i] = true;
				path[i] = next;
			}
		}
	}
	return 0;
}
/*
int dfs(int from)
{
	int i;
	if(from == n)
	{
		int min = 99999999;
		for(i = n; path[i] != -1; i = path[i])
		{
			min = min > cf[path[i]][i] ? cf[path[i]][i]:min;
		}
		return min;
	}
	u[from] = true;
	for(i = 0; i <= n; i++)
	{
		if(!u[i] && cf[from][i] > 0)
		{
			u[i] = true;
			path[i] = from;
			int flow = dfs(i);
			if(flow > 0) return flow;
			path[i] = -1;
			u[i] = false;
		}
	}
	return 0;
}*/
void solve()
{
	int min, i;
	memset(u, false, sizeof(u));
	memset(path, -1, sizeof(path));
	while((min = bfs(0)) != 0)
	{
		for(i = n - 1; i != -1; i = path[i])
		{
			//int from = path[i];
			f[path[i]][i] += min;
			f[i][path[i]] -= min;
			if(f[path[i]][i] > 0)
			{
				cf[i][path[i]] = f[path[i]][i];
				cf[path[i]][i] = cap[path[i]][i] - f[path[i]][i];
			}
		}
		memset(u, false, sizeof(u));
		memset(path, -1, sizeof(path));
	}
	__int64 maxflow = 0;
	for(i = 1; i <= n - 1; i++)
	{
		maxflow += f[0][i];
	}
	printf("%I64d\n", maxflow);
}
void makemap()
{
	//建图，初始化容量矩阵以及残留网络，确定顶点个数ｎ
	memset(f, 0, sizeof(f));
	memset(cap, 0, sizeof(cap));
	memset(cf, 0, sizeof(cf));
	int i, s, e, c;
	for(i = 1; i <= m; i++)
	{
		cin >> s >> e >> c;
		if(cap[s-1][e-1] == 0) cap[s-1][e-1] = cf[s-1][e-1] = c;
		else cap[s-1][e-1] = cf[s-1][e-1] += c;／／重边
	}
}
int main()
{
	／／freopen("in.txt", "r", stdin);
	while(cin >> m >> n)
	{
		makemap();
		solve();
	}
         return 0;
}

• 自问自答了 (2539) fishyuze 2007-03-27 22:41:13
  • 不解,难道是数据太弱，还是．．．？ (195) mayp 2007-04-13 20:47:00
    • Re:不解,难道是数据太弱，还是．．．？ (272) Yuzia 2007-05-15 14:53:09