Barricade

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as

Input

The first line of input contains an integer

Output

For each test cases, output the minimum wood cost.

Sample Input

1 4 4 1 2 1 2 4 2 3 1 3 4 3 4

Sample Output

分析：对最短路求最小割最大流即可;

代码：

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set
                     
                      ::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector
                      
                       #define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair
                       
                        #define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=1e3+10;using namespace std;ll gcd(ll p,ll q){ return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){ if(q&1)f=f*p;p=p*p;q>>=1;}return f;}int n,m,k,t,h[maxn],tot,vis[maxn],s,cur[maxn],f[maxn],d[maxn],g[maxn];vi edge[maxn];struct Node{ int x,y,z; Node(){} Node(int _x,int _y,int _z):x(_x),y(_y),z(_z){}}op[10010];struct node{ int to,nxt,cap,flow;}e[10010<<1];void add(int x,int y,int z){ e[tot].to=y; e[tot].nxt=h[x]; e[tot].cap=z; e[tot].flow=0; h[x]=tot++; e[tot].to=x; e[tot].nxt=h[y]; e[tot].flow=0; h[y]=tot++;}bool bfs(){ memset(vis,0,sizeof vis); queue
                        
                         p; p.push(s); vis[s]=1; while(!p.empty()) { int x=p.front();p.pop(); for(int i=h[x];i!=-1;i=e[i].nxt) { int to=e[i].to,cap=e[i].cap,flow=e[i].flow; if(!vis[to]&&cap>flow) { vis[to]=vis[x]+1; p.push(to); } } } return vis[t];}void pr_bfs(int s){ int i; memset(d,inf,sizeof d); memset(vis,0,sizeof vis); queue
                         
                          p;p.push(s);vis[s]=1;d[s]=0; while(!p.empty()) { int q=p.front();p.pop();vis[q]=0; for(int x:edge[q]) { if(d[x]>d[q]+1) { d[x]=d[q]+1; if(!vis[x])p.push(x),vis[x]=1; } } } if(s==n)rep(i,1,n)f[i]=d[i]; else rep(i,1,n)g[i]=d[i]; return;}int dfs(int x,int a){ if(x==t||a==0)return a; int ans=0,j; for(int&i=cur[x];i!=-1;i=e[i].nxt) { int to=e[i].to,cap=e[i].cap,flow=e[i].flow; if(vis[to]==vis[x]+1&&(j=dfs(to,min(a,cap-flow)))>0) { e[i].flow+=j; e[i^1].flow-=j; ans+=j; a-=j; if(a==0)break; } } return ans;}int max_flow(int s,int t){ int flow=0,i; while(bfs()) { memcpy(cur,h,sizeof cur); flow+=dfs(s,inf); } return flow;}int main(){ int i,j,test; scanf("%d",&test); while(test--) { tot=0; memset(h,-1,sizeof h); scanf("%d%d",&n,&m); rep(i,1,n)edge[i].clear(); rep(i,0,m-1) { int a,b,c; scanf("%d%d%d",&a,&b,&c); op[i]=Node(a,b,c); edge[a].pb(b),edge[b].pb(a); } pr_bfs(n); pr_bfs(1); rep(i,0,m-1) { int a=op[i].x,b=op[i].y,c=op[i].z; if(f[a]+g[b]+1==f[1])add(a,b,c); if(f[b]+g[a]+1==f[1])add(b,a,c); } s=n,t=1; printf("%d\n",max_flow(s,t)); } //system("Pause"); return 0;}

转载于:https://www.cnblogs.com/dyzll/p/5886751.html

你可能感兴趣的文章