记录编号	53518	评测结果	AAWATWTAAA
题目名称	塔防游戏	最终得分	60
用户昵称	Citron酱	是否通过	未通过
代码语言	C++	运行时间	2.585 s
提交时间	2013-02-28 17:28:37	内存使用	7.95 MiB

#include <cstdio>
#include <climits>

#define I_F "defence.in"
#define O_F "defence.out"

const int MAXn=1000;

struct que
{
	int x;
	que *next;
};

int n, s, t;
int map1[MAXn][MAXn]={{0}}, map2[MAXn][MAXn]={{0}};
long ds[MAXn], dt[MAXn];
int v[MAXn]={0}, h[MAXn+1]={0};
bool flag=true;
int ans=0;

void Input();
void Spfa(long*, const int&);
void Getmap2();
int Dfs(const int&, const int&);
inline int Min(const int&, const int&);
void Sap();
void Output();

int main()
{
	Input();
	Spfa(ds,s);
	Spfa(dt,t);
	Getmap2();
	Sap();
	Output();
	return 0;
}

void Input()
{
	long m;
	int a, b, c;
	freopen(I_F,"r",stdin);
	for (scanf("%d%ld%d%d",&n,&m,&s,&t); m>0; --m)
	{
		scanf("%d%d%d",&a,&b,&c);
		--a, --b;
		map1[a][b]=map1[b][a]=c;
	}
	--s, --t;
}

void Spfa(long *s, const int &x)
{
	for (int i=0; i<n; ++i)
		s[i]=-1;
	s[x]=0;
	bool f[MAXn]={false};
	f[x]=true;
	que *head, *tail, *temp;
	head=new que;
	head->x=x;
	head->next=NULL;
	tail=head;
	
	while (head!=NULL)
	{
		for (int i=0; i<n; ++i)
			if (map1[head->x][i]>0 && (s[head->x]+map1[head->x][i]<s[i] || s[i]==-1))
			{
				s[i]=s[head->x]+map1[head->x][i];
				if (!f[i])
				{
					tail->next=new que;
					tail=tail->next;
					tail->x=i;
					tail->next=NULL;
				}
			}
		temp=head;
		head=head->next;
		delete temp;
	}
}

void Getmap2()
{
	for (int i=0; i<n; ++i)
		for (int j=0; j<n; ++j)
			if (ds[j]+dt[i]-map1[i][j]==ds[t])
				map2[i][j]=map2[j][i]=1;
}

int Dfs(const int &x, const int &s)
{
	if (x==t)
		return s;
	int f=0, t, minv=INT_MAX;
	for (int i=0; i<n && f<s; ++i)
		if (map2[x][i]>0)
		{
			minv=Min(minv,v[i]);
			if (v[i]==v[x]-1)
			{
				t=Dfs(i,Min(map2[x][i],s-f));
				f+=t;
				map2[x][i]-=t;
				map2[i][x]+=t;
			}
		}
//	if (--h[v[x]++]==0)
//		flag=false;
	if (f==0)
	{
		if (--h[v[x]]==0) 
			flag=false;
		v[x]=minv+1;
	}
	return f;
}

inline int Min(const int &a, const int &b)
{
	return (a<b)?a:b;
}

void Sap()
{
	h[0]=n;
	while (flag && v[s]<=n)
		ans+=Dfs(s,INT_MAX);
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%d\n",ans);
}