View Code of Problem 3607

#include<cstdio>
#include<algorithm>
#include<ctime>
#define N 7005
#define M 1000005
using namespace std;int INF=(int)1e9;
int End[N],f[N],q[N],Go[M],Value[M],Next[M];
int x[N],y[N],flag[N][N],ans[N],num[N][N];
int cnt,n,m,i,j,E,S,T,tot,all,Count,tmp,Test,L,opt,u,v;
void add(int u,int v,int w)
{
    Go[++cnt]=v;Next[cnt]=End[u];Value[cnt]=w;End[u]=cnt;
    Go[++cnt]=u;Next[cnt]=End[v];Value[cnt]=0;End[v]=cnt;
}
int bfs()
{
    for (int i=1;i<=tot;i++) f[i]=-1;
    int h=0,t=1;q[1]=S;f[S]=0;
    while (h<t)
    {
        int k=q[++h];if (k==T) return 1;
        for (int i=End[k],x;i;i=Next[i])
            if (f[x=Go[i]]==-1&&Value[i]>0)
                f[x]=f[k]+1,q[++t]=x;
  }return 0;
}
int dinic(int k,int sum)
{
    if (k==T) return sum;int os=sum;
    for (int i=End[k],x;i&&os;i=Next[i])
        if (f[x=Go[i]]==f[k]+1&&Value[i]>0)
        {
            int flow=dinic(x,min(os,Value[i]));
            Value[i]-=flow;Value[i^1]+=flow;os-=flow;
      }
    if (sum==os) f[k]=-1;
    return sum-os;
}
int get(int u){return f[u]==u?u:f[u]=get(f[u]);}
void record(int k,int u)
{
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=E;i++)
        if (flag[x[i]][y[i]]==Count) 
            f[get(x[i])]=get(y[i]);
    get(u);num[k][0]=Count;
    for (int i=1;i<=n;i++)
        num[k][i]=(get(i)==f[u])*Count;
}
int main()
{
    scanf("%d",&Test);
    for (Count=1;Count<=Test;Count++)
    {
        scanf("%d%d%d",&n,&m,&L);
        cnt=1;E=0;S=n+1;T=tot=S+1;all=*ans=0;
        for (i=1;i<=n;i++) add(i,T,1);
        for (i=1;i<=m;i++)
        {
            scanf("%d",&opt);
            if (opt==1) scanf("%d",&u),record(i,u);
            if (opt==2) 
            {
                ++E,scanf("%d%d",&x[E],&y[E]);
                if (x[E]>y[E]) swap(x[E],y[E]);
                flag[x[E]][y[E]]=Count;
          }
            if (opt==3) 
                for (scanf("%d",&tmp);tmp;tmp--)
                {
                    scanf("%d%d",&u,&v);
                    if (u>v) swap(u,v);flag[u][v]=0;
              }
      }
      for (i=m;i;i--)
          if (num[i][0]==Count)
          {
              add(S,++tot,L);
                for (j=1;j<=n;j++)
                  if (num[i][j]==Count) add(tot,j,1);
              tmp=0;
              while (bfs())
                  tmp+=dinic(S,INF);
              ans[++*ans]=tmp;all+=tmp;
        }
      for (i=1;i<=tot;i++) End[i]=0;
      printf("%d\n",all);
      for (i=*ans;i>1;i--)
          printf("%d ",ans[i]);
      if (*ans) printf("%d\n",ans[1]);
  }
}

Double click to view unformatted code.


Back to problem 3607