记录编号	204650	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	0.395 s
提交时间	2015-11-04 15:32:53	内存使用	1.27 MiB

/*
Problem:cogs2084;
Language:c++;
by dydxh;
2015.11.03;
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#include<ctime>
#include<cstdlib>
#include<bitset>
#include<string>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=505;
const int maxm=30005;
int n,m,Coster,super_s,super_e,cnt=1,ans;
int linkk[maxn<<1];
struct edge{
	int y,next,c,v;
}e[(maxn*3)+(maxm<<1)];
inline int read(){
	int x=0;bool flag=0;char ch=getchar();
	while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
void insert(int a,int b,int c,int d){
	e[++cnt].next=linkk[a];
	linkk[a]=cnt;
	e[cnt].y=b;
	e[cnt].v=c;
	e[cnt].c=d;
	e[++cnt].next=linkk[b];
	linkk[b]=cnt;
	e[cnt].y=a;
	e[cnt].v=0;
	e[cnt].c=-d;
}
void Build_Graph(){
	n=read(),m=read(),Coster=read();
	super_s=0,super_e=n<<1|1;
	for(int i=1;i<=m;i++){
		int x=read(),y=read(),v=read();
		if(v>=Coster) continue;
		insert(x,y+n,1,v);
	}
	for(int i=1;i<=n;i++){
		insert(super_s,i,1,0);
		insert(super_s,i+n,1,Coster);
		insert(i+n,super_e,1,0);
	}
}
int head,tail;
int q[maxn+20],pos[maxn],pre[maxn],Dis[maxn];
bool vis[maxn];
bool SPFA(){
	memset(Dis,10,sizeof(Dis));
	Dis[super_s]=0,q[1]=super_s,head=0,tail=1;
	while(head!=tail){
		head++;if(head>maxn) head=1;
		int tn=q[head];
		for(int i=linkk[tn];i;i=e[i].next){
			if(e[i].v==0) continue;
			int tmp=e[i].y;
			if(Dis[tmp]>Dis[tn]+e[i].c){
				Dis[tmp]=Dis[tn]+e[i].c;
				pre[tmp]=tn,pos[tmp]=i;
				if(!vis[tmp]){
					vis[tmp]=true;
					tail++;if(tail>maxn) tail=1;
					q[tail]=tmp;
				}
			}
		}
		vis[tn]=false;
	}
	return Dis[super_e]!=Dis[super_e+1];
}
void dydxh(){
	int flow=oo;
	for(int i=super_e;i!=super_s;i=pre[i])
		if(e[pos[i]].v<flow)
			flow=e[pos[i]].v;
	ans+=flow*Dis[super_e];
	for(int i=super_e;i!=super_s;i=pre[i]){
		e[pos[i]].v-=flow;
		e[pos[i]^1].v+=flow;
	}
}
int main()
{
	//freopen("cc.in","r",stdin);
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	Build_Graph();
	while(SPFA())
		dydxh();
	printf("%d\n",ans);
	return 0;
}