首页 > 代码库 > HDU 4940(杭电多校#7 1006) Destroy Transportation system(瞎搞)

HDU 4940(杭电多校#7 1006) Destroy Transportation system(瞎搞)

题目地址:HDU 4940

当时这个题一看就看出来了是网络流的最小割,然后就一直在想建图。。然后突然发现,应该要让T集合的数目最少,不然只要有两个,那这两个的每一个都可以跑到S集合,使得T集合变小。那就只能是1个了。然后。。枚举就好了。。但是虽然觉得这么做肯定没错。。但是不敢敲。。因为当时都3个小时了才只有10个队过了。。。后来又想了几遍后觉得这样没错,就写完交上了。果然AC。。。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int ww[300][300], cc[300][300];
int main()
{
    int t, n, m, flag, u, v, w, c, i, j, x, y, num;
    while(scanf("%d",&t)!=EOF)
    {
        num=0;
        while(t--)
        {
            num++;
            scanf("%d%d",&n,&m);
            memset(ww,0,sizeof(ww));
            memset(cc,0,sizeof(cc));
            while(m--)
            {
                scanf("%d%d%d%d",&u,&v,&w,&c);
                ww[u][v]=w;
                cc[u][v]=c;
            }
            flag=0;
            for(i=1; i<=n; i++)
            {
                x=y=0;
                for(j=1; j<=n; j++)
                {
                    y+=ww[i][j]+cc[i][j];
                    x+=ww[j][i];
                }
                if(y<x)
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                printf("Case #%d: unhappy\n",num);
            else
                printf("Case #%d: happy\n",num);
        }
    }
    return 0;
}