记录编号	611607	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[THUPC 2025 pre] 检查站	最终得分	100
用户昵称	梦那边的原神	是否通过	通过
代码语言	C++	运行时间	3.267 s
提交时间	2026-01-31 15:09:52	内存使用	7.37 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+10,M=2e6+10,inf=1e8;
int n,m,c;
int S,T,d[N],ver[N],to[M],nxt[M],val[M],idx=1,now[N];
void add(int x,int y,int z){
	to[++idx]=y,nxt[idx]=ver[x],ver[x]=idx,val[idx]=z;
	to[++idx]=x,nxt[idx]=ver[y],ver[y]=idx,val[idx]=0;
}
queue<int>q;
bool bfs(){
	while(q.size())q.pop();
	for(int i=S;i<=T;i++)d[i]=0,now[i]=ver[i];
	d[S]=1,q.push(S);
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=ver[x];i;i=nxt[i]){
			if(val[i]&&!d[to[i]]){
				int y=to[i];
				d[y]=d[x]+1;
				q.push(y);
				if(y==T)return 1;	
			}
		}
	} 
	return 0;
}
int dinic(int x,int flow){
	if(x==T||!flow)return flow;
	int used=0,f,y;
	for(int i=now[x];i;i=nxt[i]){
		now[x]=i,y=to[i];
		if(val[i]&&d[y]==d[x]+1){
			f=dinic(y,min(flow-used,val[i]));
			if(!f)d[y]=0;
			else used+=f,val[i]-=f,val[i^1]+=f;
			if(used==flow)break;
		}
	}
	return used;
}
int flow(){
	int maxflow=0,incf=0;
	while(bfs()){
		while(incf=dinic(S,inf))maxflow+=incf;
	}
	return maxflow;
}
int main(){
	freopen("thupc2025_pre_checkpoint.in","r",stdin);
	freopen("thupc2025_pre_checkpoint.out","w",stdout);
	scanf("%d %d %d",&n,&m,&c);
	S=1,T=n+2*c+1;
	for(int i=1,x;i<=c;i++){
		scanf("%d",&x);
		add(n+i,n+c+i,1);
	}
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,n+w,inf);
		add(n+c+w,v,inf);
	} 
	add(n,T,inf);
	printf("%d\n",flow());
	return 0;
}