hdu 3435 A new Graph Game (최소 비용 최대 흐름)

http://acm.hdu.edu.cn/showproblem.php?pid=3435
제목: 하나의 무 방향 그림 (or 방향 그림) 은 모든 점 이 하나의 원 에 속 하고 하나의 원 에 만 속 하 며 요 구 를 만족 시 키 는 최소 비용 을 구 해 야 한다.
예 를 들 면:
1 2 5 2 3 5 3 1 10 3 4 12 4 1 8 4 6 11 5 4 7 5 6 9 6 5 4 there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42
 
이렇게 원 을 구성 하고 각 점 은 하나의 원 에 만 속 하 는 문제 로 2 분 의 그림 으로 바 꿀 수 있 으 며, 각 점 은 하나의 원 에 만 속 할 수 있다. 그러면 출 도와 입 도 는 반드시 1 이 될 것 이다. 그러면 한 점 을 뜯 어 i, i, i 로 읽 기 를 제어 한다. i ' 출력 을 제어 하고 유량 은 1 만 할 수 있다.그러면 원래 그림 에 있 는 쪽 에... i - > j`, j - > i`;연결 하여 구 도 를 한 다음 에 슈퍼 원점 s, 슈퍼 어 셈 블 리 t, s - > i, i '- > t 를 구축한다.그리고 최소 비용 흐름 을 구하 세 요.이렇게 하면 모든 점 이 하나의 원 에 만 속 할 수 있다 는 것 을 보장 한다. 입 독 때문에 출 도 = = 1;이런 것 도 괜찮아 요.  판단 적 인 문제 로
관건 은 점 을 뜯 어 그림 을 만 드 는 것 이다. 각 정점 을 i 와 i + n 으로 뜯 는 것 이다.원점 S 와 어 셈 블 리 T 를 추가 합 니 다.
S 와 1 ~ n 의 건축 변, 용량 은 1 이 고 비용 은 0 이다.
n + 1 ~ n * 2 와 T 가 변 을 만 들 고 용량 은 1 이 며 비용 은 0 입 니 다.
만약 ab 오른쪽 에 a 와 b + n 이 사 이 드 를 만 들 면 용량 은 1 이 고 c, b 와 a + n 이 사 이 드 를 만 들 면 용량 은 1 이 며 비용 은 c 이다.
최소 비용 흐름 을 구하 다.
마지막 으로 판단 할 때 모든 점 에 특정한 쌍 연결 분량 이 존재 하기 때문에 모든 점 (1 ~ n) 의 총 유량 은 0 이다.만약 어떤 점 의 총 유량 이 0 이 아니라면, 출력 NO.
그렇지 않 으 면 수출 최소 비용 흐름.

#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define inf 0x3f3f3f3f

const int maxn = 55555;
using namespace std;

queue<int>que;
struct node
{
    int u,v,f,c,next;
}edge[maxn];

int head[maxn];
bool vis[maxn];
int dis[maxn];
int pre[maxn];
int n,m,s,t,cnt;

void add(int u,int v,int f,int c)
{
	edge[cnt] = (struct node){u,v,f,c,head[u]};
	head[u] = cnt++;
	edge[cnt] = (struct node){v,u,0,-c,head[v]};
	head[v] = cnt++;
}

bool spfa()
{
    int j;
    while(!que.empty()) que.pop();
    memset(vis,false,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    memset(pre,-1,sizeof(pre));

    vis[s]=true;
    dis[s]=0;
    que.push(s);

    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;

        for(j=head[u]; j!=-1; j=edge[j].next)
        {
            int v=edge[j].v;

            if(edge[j].f&&dis[u]+edge[j].c<dis[v])
            {
                dis[v]=dis[u]+edge[j].c;
                pre[v]=j;

                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }

    return dis[t]!=inf;
}


int mincost()
{
    int ret=0,u;
    while(spfa())
    {
        u=pre[t];
        ret+=dis[t];

        while(u!=-1)
        {
            edge[u].f--;
            edge[u^1].f++;
            u=pre[edge[u].u];
        }
    }

    return ret;
}
int main()
{
    int test;
    scanf("%d",&test);
    for(int item = 1; item <= test; item++)
    {
        cnt = 0;
        memset(head,-1,sizeof(head));
        scanf("%d%d",&n,&m);
        s=0;
        t=2*n+1;

        int a,b,c;

        for(int i=1; i<=m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b+n,1,c);
            add(b,a+n,1,c);
        }

        for(int i=1; i<=n; i++)
        {
            add(s,i,1,0);
            add(i+n,t,1,0);
        }


        int ans=mincost();

        int j;
        for(j=head[s]; j!=-1; j=edge[j].next)
			if(edge[j].f!=0)
				break;

        if(j==-1) printf("Case %d: %d
",item,ans);

        else printf("Case %d: NO
",item);
    }
    return 0;
}