Destroy Transportation system
对于每一个点，£A=等效出流=破坏有向边
£B=等效入流=破坏有向边+rebulid
可以看作当存在某一集合 £B<£A时，条件不成立
可以推出，相邻两个点都不满足，则这两个点组成的集合也不会满足；不相邻的两个集合不满足，则这两个集合的合集肯定也不满足
存在一个集合不满足，则这个集合定存在一个点不满足
1 #grommaing hdoj 4940 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6 7 typedef long long ll; 8 9 ll A[201],B[201]; 10 11 void init(){ 12 memset(A,0,sizeof(A)); 13 memset(B,0,sizeof(B)); 14 } 15 16 int main() 17 { 18 int T; 19 int n,m; 20 int u,v,d,b; 21 int cas=0; 22 scanf("%d",&T); 23 while(T--){ 24 init(); 25 bool flag= false; 26 scanf("%d%d",&n,&m); 27 for(int i=0;i<m;i++){ 28 scanf("%d%d%d%d",&u,&v,&d,&b); 29 A[u] += d; //出流和£A 30 B[v] += d+b; //入流和£B 31 } 32 for(int i=1;i<=n;i++) 33 if(A[i]>B[i]){ 34 flag = true; 35 break; 36 } 37 printf("Case #%d: ",++cas); 38 if(!flag) 39 printf("happy "); 40 else 41 printf("unhappy "); 42 } 43 44 return 0; 45 }