看不懂题解以及别人说的集合最多只有一个点。。。。。
然后试了下题解的方法http://blog.sina.com.cn/s/blog_6bddecdc0102uzka.html
首先是无源汇有上下界最大流：就是最大流基础上，无源汇，每条边的流量有上下界。
这题是给一个图，V<=200，E<=5000，每条边有destroy[i][j]和build[i][j]。选一个非空点集S，令T为S的补集。若max{∑D[s][t]-D[t][s]-B[t][s]}<=0输出happy否则输出unhappy，其中s，t是点集S，点集T的结点。
转换的推导证明可以看题解链接。这里不说多成累赘。
对于无源汇有上下界最大流的解法如下http://blog.****.net/z309241990/article/details/38531655
上界用ci表示，下界用bi表示。
下界是必须流满的，那么对于每一条边，去掉下界后，其*流为ci– bi。
主要思想：每一个点流进来的流=流出去的流
对于每一个点i，令
Mi= sum(i点所有流进来的下界流)– sum(i点所有流出去的下界流)
如果Mi大于0，代表此点必须还要流出去Mi的*流，那么我们从源点连一条Mi的边到该点。
如果Mi小于0，代表此点必须还要流进来Mi的*流，那么我们从该点连一条Mi的边到汇点。
如果求S->T的最大流，看是否满流(S的相邻边都流满)。
满流则有解，否则无解。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std; // sap
#define mxn 222
#define mxe 10100 const int INF = 2100000000;
struct SAP{
int dis[mxn], pre[mxn], gap[mxn], arc[mxn], f[mxe], cap[mxe];
int head[mxn], nxt[mxe], vv[mxe], e;
void init(){e=0;memset(head,-1,sizeof(head));}
void add(int u,int v,int c) {
vv[e] = v, cap[e] = c, nxt[e] = head[u], head[u] = e++;
vv[e] = u, cap[e] = 0, nxt[e] = head[v], head[v] = e++;
}
int max_flow( int s, int t, int n ) {
int q[mxn], j, mindis, ans = 0, ht = 0, tl = 1, u, v, low;
bool found, vis[mxn];
memset( dis, 0, sizeof(dis) );
memset( gap, 0, sizeof(gap) );
memset( vis, 0, sizeof(vis) );
memset( arc, -1, sizeof(arc) );
memset( f, 0, sizeof(f) );
q[0] = t; vis[t] = true; dis[t] = 0; gap[0] = 1;
while( ht < tl ) {
u = q[ht++];
for( int i = head[u]; i != -1; i = nxt[i] ) {
v = vv[i];
if( !vis[v] ) {
vis[v] = true;
dis[v] = dis[u] + 1;
q[tl++] = v;
gap[dis[v]]++;
arc[v] = head[v];
}
}
}
u = s; low = INF; pre[s] = s;
while( dis[s] < n ) {
found = false;
for( int &i = arc[u]; i != -1; i = nxt[i] )
if( dis[vv[i]] == dis[u]-1 && cap[i] > f[i] ) {
found = true; v = vv[i];
low = min(low, cap[i]-f[i]);
pre[v] = u; u = v;
if( u == t ) {
while( u != s ) {
u = pre[u];
f[arc[u]] += low;
f[arc[u]^1] -= low;
}
ans += low; low = INF;
}
break;
}
if( found )
continue;
mindis = n;
for(int i = head[u]; i != -1; i = nxt[i] ) {
if( mindis > dis[vv[i]] && cap[i] > f[i] ) {
mindis = dis[vv[j = i]];
arc[u] = i;
}
}
gap[dis[u]]--;
if( gap[dis[u]] == 0 ) return ans;
dis[u] = mindis + 1;
gap[dis[u]]++;
u = pre[u];
}
return ans;
}
}net; int low[222];
int main(){
int t,n,m,ca=0;
scanf("%d",&t);
while(t--){
printf("Case #%d: ",++ca);
scanf("%d%d",&n,&m);
net.init();
memset(low,0,sizeof low );
for(int i=0;i<m;++i){
int u,v,d,b;
scanf("%d%d%d%d",&u,&v,&d,&b);
low[u]-=d;
low[v]+=d;
net.add(u,v,b);
}
int ans=0;
for(int i=1;i<=n;++i){
if(low[i]>0) net.add(0,i,low[i]), ans+=low[i];
if(low[i]<0) net.add(i,n+1,-low[i]);
}
int mf = net.max_flow(0,n+1,n+2);
if(mf==ans)puts("happy");
else puts("unhappy");
}
return 0;
}