特诡异的不加 GAP 优化就可以 AC, 加了就 WA.
已经证明数据无问题, 拿可以保证正确性的程序跑过了, AC.
求解为何如此, 是 GAP 写错了? 还是 GAP 优化本身有问题.
下面是代码:
----------------------WA---------------------
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

const int MMAX = 310;

long long E[MMAX][MMAX];
int D[MMAX], DN[MMAX];
int N, M, s, t;
deque<int> Q;

void BFS(int x)
{
	int i, j;
	memset(D, 0, sizeof(D));
	Q.push_back(x);
	while(!Q.empty())
	{
		i = Q.front();
		Q.pop_front();
		for(j = 1;j <= t;j += 1)
		{
			if(E[j][i] && !D[j])
			{
				D[j] = D[i] + 1;
				Q.push_back(j);
			}
		}
	}
}

int ISAP()
{
	int i, j, minD;
	long long answer = 0, value;
	int now[MMAX] = {}, pre[MMAX] = {};
	BFS(t);
	memset(DN, 0, sizeof(DN));
	for(i = 1;i <= t;i += 1)
		DN[D[i]] += 1;
	i = s;
	while(D[s] < M + 2)
	{
		if(i == t)
		{
			value = ~0u>>1;
			for(j = t;j != s;j = pre[j])
				value = min(value, E[pre[j]][j]);
			for(j = t;j != s;j = pre[j])
			{
				E[pre[j]][j] -= value;
				E[j][pre[j]] += value;
			}
			answer += value;
			i = s;
		}
		for(j = now[i];j <= t;j += 1)
		{
			if(E[i][j] && D[i] == D[j] + 1)
			{
				pre[j] = i;
				now[i] = j;
				i = j;
				break;
			}
		}
		if(j > t)
		{
			DN[D[i]] -= 1;
			if(DN[D[i]] == 0)
				break;
			minD = M + 2;
			for(j = 1;j <= t;j += 1)
			{
				if(E[i][j])
					minD = min(minD, D[j]);
			}
			D[i] = minD + 1;
			DN[D[i]] += 1;
			now[i] = 0;
			if(i != s)
				i = pre[i];
		}
	}
	return answer;
}

int main()
{
	int i, u, v, c;
	while(scanf("%d %d", &N, &M) != EOF)
	{
		memset(E, 0, sizeof(E));
		s = M + 1;
		t = M + 2;
		E[s][1] = ~0u>>1;
		E[M][t] = ~0u>>1;
		for(i = 1;i <= N;i += 1)
		{
			scanf("%d %d %d", &u, &v, &c);
			E[u][v] += c;
		}
		printf("%d\n", ISAP());
	}
	exit(0);
}

-----------------------------AC-------------------------
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

const int MMAX = 310;

long long E[MMAX][MMAX];
int D[MMAX], DN[MMAX];
int N, M, s, t;
deque<int> Q;

void BFS(int x)
{
	int i, j;
	memset(D, 0, sizeof(D));
	Q.push_back(x);
	while(!Q.empty())
	{
		i = Q.front();
		Q.pop_front();
		for(j = 1;j <= t;j += 1)
		{
			if(E[j][i] && !D[j])
			{
				D[j] = D[i] + 1;
				Q.push_back(j);
			}
		}
	}
}

int ISAP()
{
	int i, j, minD;
	long long answer = 0, value;
	int now[MMAX] = {}, pre[MMAX] = {};
	BFS(t);
	memset(DN, 0, sizeof(DN));
	for(i = 1;i <= t;i += 1)
		DN[D[i]] += 1;
	i = s;
	while(D[s] < M + 2)
	{
		if(i == t)
		{
			value = ~0u>>1;
			for(j = t;j != s;j = pre[j])
				value = min(value, E[pre[j]][j]);
			for(j = t;j != s;j = pre[j])
			{
				E[pre[j]][j] -= value;
				E[j][pre[j]] += value;
			}
			answer += value;
			i = s;
		}
		for(j = now[i];j <= t;j += 1)
		{
			if(E[i][j] && D[i] == D[j] + 1)
			{
				pre[j] = i;
				now[i] = j;
				i = j;
				break;
			}
		}
		if(j > t)
		{
			DN[D[i]] -= 1;
			//if(DN[D[i]] == 0) <----------------
			//	break; <---------------------
                        //去掉这两行就 AC, 取消注释就 WA
			minD = M + 2;
			for(j = 1;j <= t;j += 1)
			{
				if(E[i][j])
					minD = min(minD, D[j]);
			}
			D[i] = minD + 1;
			DN[D[i]] += 1;
			now[i] = 0;
			if(i != s)
				i = pre[i];
		}
	}
	return answer;
}

int main()
{
	int i, u, v, c;
	while(scanf("%d %d", &N, &M) != EOF)
	{
		memset(E, 0, sizeof(E));
		s = M + 1;
		t = M + 2;
		E[s][1] = ~0u>>1;
		E[M][t] = ~0u>>1;
		for(i = 1;i <= N;i += 1)
		{
			scanf("%d %d %d", &u, &v, &c);
			E[u][v] += c;
		}
		printf("%d\n", ISAP());
	}
	exit(0);
}

--------------------可保正确性----------------------------

#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

const int NMAX = 210;

int E[NMAX][NMAX], pre[NMAX];
int M, N;
deque<int> Q;

int dinic()
{
	int i, j, answer = 0, value;
	while(1)
	{
		memset(pre, 0, sizeof(pre));
		Q.push_back(1);
		while(!Q.empty())
		{
			i = Q.front();
			Q.pop_front();
			for(j = 1;j <= N;j += 1)
			{
				if(E[i][j] && !pre[j])
				{
					pre[j] = i;
					Q.push_back(j);
				}
			}
		}
		if(!pre[N])
			return answer;
		value = ~0u>>1;
		for(i = N;i != 1;i = pre[i])
			value = min(value, E[pre[i]][i]);
		for(i = N;i != 1;i = pre[i])
		{
			E[pre[i]][i] -= value;
			E[i][pre[i]] += value;
		}
		answer += value;
	}
	return answer;
}

int main()
{
	int i, u, v, z;
	for(;scanf("%d %d", &M, &N) != EOF;)
	{
		memset(E, 0, sizeof(E));
		for(i = 1;i <= M;i += 1)
		{
			scanf("%d %d %d", &u, &v, &z);
			E[u][v] += z;
		}
		printf("%d\n", dinic());
	}
	exit(0);
}

• 原来是初始化的问题... (193) braveTester 2012-03-27 00:09:26