记录编号	204477	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	100
用户昵称	前鬼后鬼的守护	是否通过	通过
代码语言	C++	运行时间	0.842 s
提交时间	2015-11-04 12:53:00	内存使用	39.46 MiB

#include<cstdio>
#include<cstring>
inline int read(){
	int x=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+ch-'0',ch=getchar();return x;
}
const int MAXV=500,MAXC=10000,D=10;
struct edge{
	int y,f,v,next;
	static int tot;
}e[MAXV*MAXV*D];
int edge::tot,head[MAXV+D],S,T;
inline void connect(int s,int t,int f,int v){
	int k1=(++edge::tot)<<1,k2=k1|1;
	e[k1].y=t,e[k1].f=f,e[k1].v=v,e[k1].next=head[s],head[s]=k1;
	e[k2].y=s,e[k2].f=0,e[k2].v=-v,e[k2].next=head[t],head[t]=k2;
}
int dis[MAXV+D],flow[MAXV+D],prev[MAXV+D];bool inque[MAXV+D];
int que[MAXV*10+D],fro,rear;
int n,m,k,a[MAXV+D][MAXV+D],ans;
void init(){
	memset(a,127,sizeof a);
	n=read(),m=read(),k=read();S=0,T=(n<<1)|1;
	for(int i=1;i<=m;i++){
		int s=read(),t=read(),v=read();
		if(v<a[s][t])a[s][t]=v;
	}
	for(int i=1;i<=n;i++){
		connect(S,i,1,0);
		for(int j=1;j<=n;j++)
			if(a[i][j]<=MAXC)
				connect(i,j+n,1,a[i][j]);
		connect(S,i+n,1,k);
		connect(i+n,T,1,0);
	}
}
int SPFA(){
	memset(dis,50,sizeof dis);
	memset(flow,50,sizeof flow);
	fro=0,rear=-1,que[++rear]=S,dis[S]=0,inque[S]=true;
	while(fro<=rear){
		int x=que[fro++];inque[x]=false;
		if(x==T)continue;
		for(int i=head[x];i;i=e[i].next)if(e[i].f){
			int y=e[i].y,v=e[i].v;
			if(dis[x]+v<dis[y]){
				dis[y]=dis[x]+v;
				if(flow[x]<flow[y])flow[y]=flow[x];
				if(e[i].f<flow[y])flow[y]=e[i].f;
				prev[y]=i;
				if(!inque[y])que[++rear]=y,inque[y]=true;
			}
		}
	}
	if(flow[T]>=10000)return 0;
	for(int x=T,d=flow[T];x!=S;x=e[prev[x]^1].y)
		e[prev[x]].f-=d,e[prev[x]^1].f+=d;
	return flow[T]*dis[T];
}
void mincost_maxflow(){
	for(int d=SPFA();d;d=SPFA())
		ans+=d;
}
int main(){
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	init();
	mincost_maxflow();
	printf("%d",ans);
	return 0;
}