HDu 3452(最小割)

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=3452
構想:辺権のある木で、最小に木の根と葉の結点がつながっていないことを求めます.汇点をn+1とすることができ、叶结点のみが汇点连容量infの辺であることに注意する.


View Code

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cmath>

  5 #include<set>

  6 using namespace std;

  7 #define MAXN 2222

  8 #define MAXM 222222

  9 #define inf 1<<30

 10 

 11 struct Edge{

 12     int v,cap,next;

 13 }edge[MAXM];

 14 

 15 

 16 int head[MAXN];

 17 int pre[MAXN];

 18 int cur[MAXN];

 19 int level[MAXN];

 20 int gap[MAXN];

 21 int NV,NE,n,m,vs,vt;

 22 

 23 void Insert(int u,int v,int cap,int cc=0){

 24     edge[NE].v=v;edge[NE].cap=cap;

 25     edge[NE].next=head[u];head[u]=NE++;

 26 

 27     edge[NE].v=u;edge[NE].cap=cc;

 28     edge[NE].next=head[v];head[v]=NE++;

 29 }

 30 

 31 

 32 int SAP(int vs,int vt){

 33     memset(pre,-1,sizeof(pre));

 34     memset(level,0,sizeof(level));

 35     memset(gap,0,sizeof(gap));

 36     for(int i=0;i<=NV;i++)cur[i]=head[i];

 37     int u=pre[vs]=vs,maxflow=0,aug=-1;

 38     gap[0]=NV;

 39     while(level[vs]<NV){

 40 loop:

 41         for(int &i=cur[u];i!=-1;i=edge[i].next){

 42             int v=edge[i].v;

 43             if(edge[i].cap&&level[u]==level[v]+1){

 44                 aug==-1?aug=edge[i].cap:aug=min(aug,edge[i].cap);

 45                 pre[v]=u;

 46                 u=v;

 47                 if(v==vt){

 48                     maxflow+=aug;

 49                     for(u=pre[u];v!=vs;v=u,u=pre[u]){

 50                         edge[cur[u]].cap-=aug;

 51                         edge[cur[u]^1].cap+=aug;

 52                     }

 53                     aug=-1;

 54                 }

 55                 goto loop;

 56             }

 57         }

 58         int minlevel=NV;

 59         for(int i=head[u];i!=-1;i=edge[i].next){

 60             int v=edge[i].v;

 61             if(edge[i].cap&&minlevel>level[v]){

 62                 cur[u]=i;

 63                 minlevel=level[v];

 64             }

 65         }

 66         if(--gap[level[u]]==0)break;

 67         level[u]=minlevel+1;

 68         gap[level[u]]++;

 69         u=pre[u];

 70     }

 71     return maxflow;

 72 }

 73 

 74 int main(){

 75     while(~scanf("%d%d",&n,&m)&&n&&m){

 76         vs=m,vt=n+1,NV=vt,NE=0;

 77         memset(head,-1,sizeof(head));

 78         set<int>st[MAXN];

 79         for(int i=1;i<=n-1;i++){

 80             int u,v,w;

 81             scanf("%d%d%d",&u,&v,&w);

 82             Insert(u,v,w);

 83             Insert(v,u,w);

 84             st[u].insert(v);

 85             st[v].insert(u);

 86         }

 87         //              inf  

 88         for(int i=0;i<=n;i++){

 89             if(st[i].size()==1&&i!=vs)Insert(i,vt,inf);

 90         }

 91         printf("%d
",SAP(vs,vt));

 92     }

 93     return 0;

 94 }

 95 

 96 

 97     

 98 

 99 

100 

101 

102 

103     

104     

105