职务地址： pid=4940">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;
}
版权声明：本文博主原创文章，博客，未经同意不得转载。