思路：无源汇有上下界可行流判定， 原来每条边转化成 下界为D 上界为 D+B ，判断是否存在可行流即可。
为什么呢？ 如果存在可行流 那么说明对于任意的 S 集合流出的肯定等于 流入的， 流出的计算的 X 肯定小于等于这个流量（X是下界之和）， 计算出来的Y （上界之和）肯定大于等于 这个流量 肯定满足X<=Y。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include <iostream>
#include<climits>
using namespace std;
const int N = ;
const int M = ;
int n;
int ecnt, head[N], nx[M], to[M], va[M], cur_edge[N];
int source, target, flow, pre[N], lev[N], qu[N], sign;
void addedge(int u, int v, int w) {
to[ecnt] = v;
nx[ecnt] = head[u];
va[ecnt] = w;
head[u] = ecnt++;
}
bool bfs(int s, int t) {
std::fill(lev, lev + n, -);
sign = t;
lev[t] = ;
int st = , ed = ;
qu[ed++] = t;
while (st != ed && lev[s] == -) {
int u = qu[st++];
for (int i = head[u]; i != -; i = nx[i]) {
if (va[i ^ ] > && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
qu[ed++] = to[i];
}
}
}
return lev[s] != -;
}
void push() {
int delta = INT_MAX, u, p;
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
delta = std::min(delta, va[p]);
}
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
va[p] -= delta;
if (!va[p]) {//注意double时要改
sign = to[p ^ ];
}
va[p ^ ] += delta;
}
flow += delta;
}
void dfs(int u) {
if (u == target)
push();
else {
for (int i = cur_edge[u]; i != -; i = nx[i]) {
if (va[i] > && lev[u] == lev[to[i]] + ) {
pre[to[i]] = i;
dfs(to[i]);
if (lev[sign] > lev[u]) {
return;
}
sign = target;
}
}
lev[u] = -;
}
}
int nc, pc, tc;
int lx[M], ly[M], lv[M];
void dinic(int s, int t, int node_cnt) {
source = s;
target = t;
n = node_cnt; //construct graph flow = ;
while (bfs(source, target)) {
for (int i = ; i < n; ++i) {
cur_edge[i] = head[i];
}
dfs(source);
} }
int in[],out[];
void solve() {
int n,m;
memset(in,,sizeof(in));
memset(out,,sizeof(out));
scanf("%d%d",&n,&m);
fill(head,head+n+,-);
ecnt=;
for(int i=;i<m;++i)
{
int u,v,x,y;
scanf("%d%d%d%d",&u,&v,&x,&y);
in[v]+=x;
in[u]-=x;
addedge(u,v,y);
addedge(v,u,);
}
int s,t;
s=;t=n+;
int sum=;
for(int i=;i<=n;++i)
{
if(in[i]>)
{
sum+=in[i];
addedge(s,i,in[i]);
addedge(i,s,);
}
else
{
addedge(i,t,-in[i]);
addedge(t,i,);
}
}
dinic(s,t,t+);
if(flow==sum)puts("happy");
else puts("unhappy");
}
int main() {
int ri=,tt;
scanf("%d",&tt);
while(tt--)
{
printf("Case #%d: ",++ri);
solve();
}
return ;
}