首页 > 其他 > 详细

hdoj 4940 强连通

时间:2016-03-22 19:04:48      阅读:136      评论:0      收藏:0      [点我收藏+]
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\n");
40         else
41             printf("unhappy\n");
42     }
43 
44     return 0;
45 }

 

  

hdoj 4940 强连通

原文:http://www.cnblogs.com/EdsonLin/p/5307958.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!