#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <vector> #include <map> #include <queue> #include <set> #include <algorithm> #include <limits> using namespace std; typedef long long LL; const int MAXN=1e+4; const int MAXM=1e+5; const int INF = numeric_limits<int>::max(); const LL LL_INF= numeric_limits<LL>::max(); struct Edge { int to,ci,next; Edge(){} Edge(int _to,int _ci,int _next):to(_to),ci(_ci),next(_next){} }e[MAXM]; int head[MAXN],tot; void init(){ memset(head,-1,sizeof(head)); tot=0; } void AddEdge(int u,int v,int ci0,int ci1=0){ e[tot]=Edge(v,ci0,head[u]); head[u]=tot++; e[tot]=Edge(u,ci1,head[v]); head[v]=tot++; } int dis[MAXN],sta[MAXN],top,cur[MAXN]; bool bfs(int st,int et){ memset(dis,0,sizeof(dis)); dis[st]=1; queue <int> q; q.push(st); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=head[now];~i;i=e[i].next) if(e[i].ci&&!dis[e[i].to]){ dis[e[i].to]=dis[now]+1; q.push(e[i].to); } } return dis[et]!=0; } LL Dinic(int st,int et){ LL ans=0; while(bfs(st,et)){ top=0; memcpy(cur,head,sizeof(head)); int u=st,i; while(1){ if(u==et){ int pos,minn=INF; for(i=0;i<top;i++){ if(minn>e[sta[i]].ci){ minn=e[sta[i]].ci; pos=i; } } for(i=0;i<top;i++){ e[sta[i]].ci-=minn; e[sta[i]^1].ci+=minn; } top=pos; u=e[sta[top]^1].to; ans+=minn; } for(i=cur[u];~i;cur[u]=i=e[i].next) if(e[i].ci&&dis[u]+1==dis[e[i].to])break; if(cur[u]!=-1){ sta[top++]=cur[u]; u=e[cur[u]].to; } else { if(top==0)break; dis[u]=0; u=e[sta[--top]^1].to; } } } return ans; } int du[MAXN],ru[MAXN],chu[MAXN],n,m; int main() { int t,cas=0; scanf("%d",&t); while(t--){ init(); scanf("%d%d",&n,&m); int st=0,et=n+1; memset(du,0,sizeof(du)); memset(ru,0,sizeof(ru)); memset(chu,0,sizeof(chu)); for(int i=0,x,y,v;i<m;i++){ scanf("%d%d%d",&x,&y,&v); chu[x]++; ru[y]++; if(v){ AddEdge(x,y,INF-1); du[x]-=1; du[y]+=1; } else { AddEdge(x,y,INF); } } for(int i=1;i<=n;i++){ if(ru[i]==0){ AddEdge(st,i,INF); } if(chu[i]==0){ AddEdge(i,et,INF); } } int sst=et+1,eet=et+2; LL ctot=0; for(int i=1;i<=n;i++){ if(du[i]>0)AddEdge(sst,i,du[i]),ctot+=du[i]; else AddEdge(i,eet,-du[i]); } LL ans=Dinic(sst,eet); AddEdge(et,st,INF); LL t=Dinic(sst,eet); printf("Case #%d: %lld\n",++cas,t); } return 0; }
|