bzoj4519: [Cqoi2016]不同的最小割（分治最小割）

时间：2021-01-01 14:30:14

4519: [Cqoi2016]不同的最小割

题目：传送门

题解：

　　 同BZOJ 2229

　　 基本一样的题目啊，就最后用set记录一下就ok

代码：

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<set>

 using namespace std;

 const int inf=;

 struct node

 {

     int x,y,c,next,other;

 }a[];int len,last[];

 int st,ed,n,m,T,ans;

 void ins(int x,int y,int c)

 {

     int k1,k2;

     k1=++len;

     a[len].x=x;a[len].y=y;a[len].c=c;

     a[len].next=last[x];last[x]=len;

     k2=++len;

     a[len].x=y;a[len].y=x;a[len].c=c;

     a[len].next=last[y];last[y]=len;

     a[k1].other=k2;

     a[k2].other=k1;

 }

 int list[],h[],head,tail;

 bool bt_h()

 {

     memset(h,,sizeof(h));h[st]=;

     list[]=st;head=;tail=;

     while(head!=tail)

     {

         int x=list[head];

         for(int k=last[x];k;k=a[k].next)

         {

             int y=a[k].y;

             if(h[y]== && a[k].c)

             {

                 h[y]=h[x]+;

                 list[tail++]=y;

             }

         }

         head++;

     }

     if(h[ed])return true;

     return false;

 }

 int find_flow(int x,int flow)

 {

     if(x==ed)return flow;

     int s=,t;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(h[y]==h[x]+ && a[k].c && s<flow)

         {

             s+=t=find_flow(y,min(a[k].c,flow-s));

             a[k].c-=t;a[a[k].other].c+=t;

         }

     }

     if(s==)h[x]=;

     return s;

 }

 int d[],num[],sta[],anss[][];

 void re_num(int x)

 {

     num[x]=;

     for(int k=last[x];k;k=a[k].next)

     {

         int y=a[k].y;

         if(a[k].c && !num[y])

             re_num(y);

     }

 }

 void solve(int l,int r)

 {

     if(l==r)return ;

     for(int i=;i<=len;i+=)a[i].c=a[i+].c=(a[i].c+a[i+].c)>>;

     st=d[l];ed=d[r];ans=;

     while(bt_h())ans+=find_flow(st,inf);

     memset(num,,sizeof(num));

     re_num(st);

     for(int i=;i<=n;i++)

         if(num[i])

             for(int j=;j<=n;j++)

                 if(!num[j])

                     anss[i][j]=anss[j][i]=min(anss[i][j],ans);

     int L=l,R=r;

     for(int i=l;i<=r;i++)

     {

         if(num[d[i]])sta[L++]=d[i];

         else      sta[R--]=d[i];

     }

     for(int i=l;i<=r;i++)d[i]=sta[i];

     solve(l,L-);solve(R+,r);

 }

 set<int> q;

 set<int> :: iterator it;

 int main()

 {

     scanf("%d%d",&n,&m);

     len=;memset(last,,sizeof(last));int x,y,c;

     for(int i=;i<=m;i++)scanf("%d%d%d",&x,&y,&c),ins(x,y,c);

     for(int i=;i<=n;i++)d[i]=i;memset(anss,,sizeof(anss));

     solve(,n);

     for(int i=;i<=n;i++)

         for(int j=i+;j<=n;j++)

             q.insert(anss[i][j]);

     printf("%d\n",q.size());

     return ;

 }

相关文章