- #include
- #include
- #include
- #defineinf 1e9#defineMax 150using namespace std;
- struct node
- {
- int next,to,dis;
- }edge[Max*Max];
- intAnswer,head[Max*Max],cnt=1,n,m,e,dep[Max*Max];
- voidadd(intu,intv,int l)
- {
- node*w=&edge[++cnt];
- w->next=head[u];
- w->to=v;
- w->dis=l;
- head[u]=cnt;
- }
- boolbfs(ints,int t)
- {
- for(inti=1;i<=n;++i) dep[i]=inf;
- dep[s]=0;
- queue<int>q;
- q.push(s);
- while(!q.empty())
- {
- inttp=q.front();
- q.pop();
- for(inti=head[tp];i;i=edge[i].next)
- {
- intv=edge[i].to;
- if(dep[v]>dep[tp]+1&&edge[i].dis)
- {
- dep[v]=dep[tp]+1;
- if(v==t)return 1;
- q.push(v);
- }
- }
- }
- return 0;
- }
- intdfs(ints,intt,int came_flow)
- {
- if(s==t||came_flow==0)return came_flow;
- intres=0,f;
- for(inti=head[s];i;i=edge[i].next)
- {
- intv=edge[i].to;
- if(dep[v]==dep[s]+1&&edge[i].dis&&(f=dfs(v,t,min(came_flow,edge[i].dis))))
- {
- res+=f;
- came_flow-=f;
- edge[i].dis-=f;
- edge[i^1].dis+=f;
- }
- if(came_flow==0)break;
- }
- return res;
- }
- intdinic(ints,int t)
- {
- while(bfs(s,t)) Answer+=dfs(s,t,inf);
- return Answer;
- }
- int main()
- {
- scanf("%d%d",&n,&e);
- for(intx,y,z;e--;)
- {
- scanf("%d%d%d",&x,&y,&z);
- add(x,y,z);
- add(y,x,z);
- }
- scanf("%d",&m);
- for(intx;m--;)
- {
- scanf("%d",&x);
- add(x,n,inf);
- add(n,x,inf);
- }
- printf("%d",dinic(1,n));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-1988068.html