记录编号	22795	评测结果	AAAAAAAAAA
题目名称	总流量	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2010-12-26 22:00:06	内存使用	0.26 MiB

#include <cstdio>
#include <cstring>

using namespace std;

int capacity[52][52];//全局变量自动初始化为 0
int E;

#define MN(x,y) ((x) < (y) ? (x) : (y))

int main()
{
	FILE *inFile = fopen("tflow.in", "rt");
	fscanf(inFile, "%i", &E);
	for(int i = 0 ; i < E ; i++)
	{
		char a,b;
		int c;
		fscanf(inFile, "%*c%c%*c%c%i", &a, &b, &c);
		if(a >= 'a' && a <= 'z')
			a += 'Z' + 1 - 'a';
		if(b >= 'a' && b <= 'z')
			b += 'Z' + 1 - 'a';
		capacity[a - 'A'][b - 'A'] += c;
		capacity[b - 'A'][a - 'A'] += c;
	}
	fclose(inFile);
	
	bool changed;//flag to tell us if the graph has changed this iteration
	do
	{
		changed = false;
		for(int i = 0 ; i < 52 ; i++)
		if(i != 0 && i != 25)
		{
			int first = -1;
			int second = -1;
			bool bad = false;
			for(int j = 0 ; j < 52 ; j++)
			{
				if(capacity[i][j] != 0)
				{
					if(first == -1)
						first = j;
					else if(second == -1)
						second = j;
					else
						bad = true;
				}
			}
//bad is set if vertex i has more than three pipes connected to it
			if(bad)continue;
			if(second != -1)//use the first simplification rule
			{
				capacity[first][second] += MN(capacity[first][i], capacity[i][second]);
				capacity[second][first] += MN(capacity[first][i], capacity[i][second]);
				capacity[first][i] = 0;
				capacity[second][i] = 0;
				capacity[i][first] = 0;
				capacity[i][second] = 0;
				
				changed = true;
			}
			else if(first != -1)//use the third simplification rule
			{
				capacity[first][i] = capacity[i][first] = 0;
				changed = true;
			}
		}
	}while(changed);
	
	FILE *outFile = fopen("tflow.out", "wt");
	fprintf(outFile, "%i\n", capacity[0][25]);
	fclose(outFile);
	
	return 0;
}