Harry Potter and the Forbidden Forest

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1155 Accepted Submission(s): 404

Problem Description Harry Potter notices some Death Eaters try to slip into Castle. The Death Eaters hide in the most depths of Forbidden Forest. Harry need stop them as soon as.

The FZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcmJpZGRlbiBGb3Jlc3QgaXMgbXlzdGVyaW91cy4gSXQgY29uc2lzdHMgb2YgTiBub2RlcyBudW1iZXJlZCBmcm9tIDAgdG8gTi0xLiBBbGwgb2YgRGVhdGggRWF0ZXJzIHN0YXkgaW4gdGhlIG5vZGUgbnVtYmVyZWQgMC4gVGhlIHBvc2l0aW9uIG9mIENhc3RsZSBpcyBub2RlIG4tMS4gVGhlIG5vZGVzIGNvbm5lY3RlZCBieSBzb21lIHJvYWRzLiBIYXJyeSBuZWVkIGJsb2NrIHNvbWUgcm9hZHMgYnkgbWFnaWMgYW5kIGhlIHdhbnQgdG8gbWluaW1pemUKIHRoZSBjb3N0LiBCdXQgaXShr3Mgbm90IGVub3VnaCwgSGFycnkgd2FudCB0byBrbm93IGhvdyBtYW55IHJvYWRzIGFyZSBibG9ja2VkIGF0IGxlYXN0LgogCjxicj4KSW5wdXQKSW5wdXQgY29uc2lzdHMgb2Ygc2V2ZXJhbCB0ZXN0IGNhc2VzLjxicj4KPGJyPgpUaGUgZmlyc3QgbGluZSBpcyBudW1iZXIgb2YgdGVzdCBjYXNlLjxicj4KPGJyPgpFYWNoIHRlc3QgY2FzZSwgdGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIG4sIG0sIHdoaWNoIG1lYW5zIHRoZSBudW1iZXIgb2Ygbm9kZXMgYW5kIGVkZ2VzIG9mIHRoZSBncmFwaC4gRWFjaCBub2RlIGlzIG51bWJlcmVkIDAgdG8gbi0xLjxicj4KPGJyPgpGb2xsb3dpbmcgbSBsaW5lcyBjb250YWlucyBpbmZvcm1hdGlvbiBhYm91dCBlZGdlcy4gRWFjaCBsaW5lIGhhcyBmb3VyIGludGVnZXJzIHUsIHYsIGMsIGQuIFRoZSBmaXJzdCB0d28gaW50ZWdlcnMgbWVhbiB0d28gZW5kcG9pbnRzIG9mIHRoZSBlZGdlcy4gVGhlIHRoaXJkIG9uZSBpcyBjb3N0IG9mIGJsb2NrIHRoZSBlZGdlLiBUaGUgZm91cnRoIG9uZSBtZWFucyBkaXJlY3RlZCAoZCA9IDApIG9yIHVuZGlyZWN0ZWQgKGQgPSAxKS48YnI+Cjxicj4KVGVjaG5pY2FsIFNwZWNpZmljYXRpb248YnI+Cjxicj4KMS4gMiA8PSBuIDw9IDEwMDA8YnI+CjIuIDAgPD0gbSA8PSAxMDAwMDA8YnI+CjMuIDAgPD0gdSwgdiA8PSBuLTE8YnI+CjQuIDAgPCBjIDw9IDEwMDAwMDA8YnI+CjUuIDAgPD0gZCA8PSAxPGJyPgoKIAo8YnI+Ck91dHB1dApGb3IgZWFjaCB0ZXN0IGNhc2U6PGJyPgpPdXRwdXQgdGhlIGNhc2UgbnVtYmVyIGFuZCB0aGUgYW5zd2VyIG9mIGhvdyBtYW55IHJvYWRzIGFyZSBibG9ja2VkIGF0IGxlYXN0Ljxicj4KCiAKPGJyPgpTYW1wbGUgSW5wdXQKCjxwcmUgY2xhc3M9"brush:java;">3 4 5 0 1 3 0 0 2 1 0 1 2 1 1 1 3 1 1 2 3 3 1 6 7 0 1 1 0 0 2 1 0 0 3 1 0 1 4 1 0 2 4 1 0 3 5 1 0 4 5 2 0 3 6 0 1 1 0 0 1 2 0 1 1 1 1 1 2 1 0 1 2 1 0 2 1 1 1
Sample Output

Case 1: 3
Case 2: 2
Case 3: 2
题意：求割边最少的最小割，
解题思路：在建图时，每个边权乘以一个大的数，然后加1,求出最大流取模，顺便就可以得到边数。
代码：
/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-25 12:19:41
File Name :3.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include 
   
    
#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; const __int64 inf=10000000000000LL; const int maxn=100010; int head[maxn],tol,dep[maxn],n; struct node { int from,to,next; __int64 cap; }edge[1000000]; void add(int u,int v,__int64 cap) { edge[tol]=(node){ u,v,head[u],cap }; head[u]=tol++; edge[tol]=(node){ v,u,head[v],0 }; head[v]=tol++; } int bfs(int s,int t) { int que[maxn],front=0,rear=0; memset(dep,-1,sizeof(dep)); dep[s]=0;que[rear++]=s; while(front!=rear) { int u=que[front++];front%=maxn; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1;

hdu 3987 最小割(一)

Harry Potter and the Forbidden Forest