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

• 不解,难道是数据太弱，还是．．．？ (195) mayp 2007-04-13 20:47:00
  • Re:不解,难道是数据太弱，还是．．．？ (272) Yuzia 2007-05-15 14:53:09