hust 1342 (상하계의 최소 흐름 있음)

Cheat Secretly

Time Limit: 1 Sec  
Memory Limit: 128 MB
Submissions: 269  
Solved: 77

Description

HH Big Cow(HBC) has taken part in an interesting treasure finding match. In the match there are N transmitting nodes(labeled from 1 to N), and between these nodes there are M directional roads. In the middle of some roads there may be a “gift-spot”, where a beautiful girl gives a gift to the contestant who passes that road. The one who gets most gifts wins! Winning the match is so easy for HBC, so he is thinking of a more challenging thing —— collecting gifts from ALL the girls. HBC has an amazing ability to achieve this goal: When he comes to a dead end, he can transfer himself to another node arbitrarily. With that ability, of course he can achieve the goal of meeting all the girls, however, cheating is not good! So he decides to use the ability as few as possible. Now he wants to know the fewest times he should use that ability to achieve his goal. NOTE:  1. The graph in the match is a directed acyclic graph (DAG). 2. There is at most one road between any two nodes.

Input

The input contains multiple case. Line 1 an integer T : number of test cases. Line 2 two integer N, M: N for number of nodes. (2 <= N <= 500) M for number of roads. (1 <= M <= 10000) Lines 3..M+2 each line three integers a, b, c: representing a directed roads from a to b. (1 <= a, b <= N) c = 1, then there is a gift spot on this road. c = 0, then there is no gift spot on this road.

Output

For each case output one line representing the fewest number of ability HBC should use.

Sample Input

2

4 2

1 2 1
3 4 1

6 7

1 2 1
2 3 1
3 4 1
1 4 0
5 2 1
3 6 1
5 6 0

Sample Output

Case #1: 2
Case #2: 2

HINT

Source

Yang Xiaobin, HUST Campus 2009
호수를 떠난 지 오래되어 황폐해졌다. 그런데 이 문제는 그날 코드wa를 두드리고 오늘에야 A가 떨어졌다. 우선 구도가 틀렸다. 그리고 각종 디버그...
제목 링크:http://acm.hust.edu.cn/thx/problem.php?id=1342
분석: 이 문제는 상하계의 최소 흐름이 뚜렷하다. 구도가 비교적 간단하다. 먼저 읽은 가장자리를 연결한 다음에 하나의 원점을 추가한다. 원점은 모든 점을 연결하고 모든 점은 외환점을 연결한다. 선물이 있는 가장자리ij는 in[i]에서 1을 줄이고 in[j]에서 1을 추가한다. 마지막으로 하나의 원점을 추가한다. 모든 점의 in을 정적인 연결원으로 하고 in은 마이너스의 연결을 해서 하나의 최대 흐름을 구하고 원래의 외환원을 연결한다.다시 최대 흐름을 구하면, 이때 원래의 원천이 송금되면 답이 된다.
코드:

#include<cstdio>
using namespace std;
const int mm=111111;
const int mn=1111;
const int oo=1000000000;
int node,src,dest,edge,n,m;
int ver[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn],in[mn];
inline int min(int a,int b)
{
    return a<b?a:b;
}
inline void prepare(int _node,int _src,int _dest)
{
    node=_node,src=_src,dest=_dest;
    for(int i=0; i<node; ++i)head[i]=-1;
    edge=0;
}
inline void addedge(int u,int v,int c)
{
    ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; ++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0; l<r; ++l)
        for(i=head[u=q[l]]; i>=0; i=next[i])
            if(flow[i]&&dis[v=ver[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp; i>=0; i=next[i])
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
void Dinic_flow()
{
    while(Dinic_bfs())
    {
        for(int i=0; i<node; ++i)work[i]=head[i];
        while(Dinic_dfs(src,oo));
    }
}
int limit_min_flow()
{
    int i,src0,dest0,edge0;
    src0=src,dest0=dest,edge0=edge;
    src=node++,dest=node++;
    head[src]=head[dest]=-1;
    for(i=1; i<=n; ++i)
    {
        if(in[i]>0)addedge(src,i,in[i]);
        if(in[i]<0)addedge(i,dest,-in[i]);
    }
    Dinic_flow();
    addedge(dest0,src0,oo);
    Dinic_flow();
    for(i=head[dest0]; i>=0; i=next[i])
        if(ver[i]==src0)return flow[i^1];
}
int main()
{
    int i,u,v,k,c,t,cas=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        prepare(n+2,0,n+1);
        for(i=1; i<=n; ++i)
            addedge(src,i,oo),addedge(i,dest,oo),in[i]=0;
        for(i=1; i<=m; ++i)
        {
            scanf("%d%d%d",&u,&v,&c);
            if(c)--in[u],++in[v];
            addedge(u,v,oo);
        }
        printf("Case #%d: %d
",++cas,limit_min_flow());
    }
    return 0;
}