http://www.lydsy.com/JudgeOnline/problem.php?id=4344

码农题+常数优化 啊 啊 啊。。。14K+

#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
using namespace std;
inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}
struct edge
{
    int id1,id2;
    bool operator <(const edge &temp)const
    {
        if(id1==temp.id1)
           return id2<temp.id2;
        return id1<temp.id1;
    }
};
edge e[501000];
bool vis[501000];
int nu[501000],sz[501000];
int *adj[501000],*vec[501000],*belong[501000],*ie[501000],*dyn[501000],*gn[501000],*fg[501000],*ag[501000];
int n,m,pa[501000],ps[501000],num_cir,list[501000],cnt_list,pos[501000],cover[501000],bel[501000];
int dp[501000],g[501000],f[1001000],awp[1001000],ans[501000],queue[501000],idx[501000],pm[501000];
int  nxt[2][501000],gs[2][501000],nc[501000];
void dfs(int id)
{
    vis[id]=true;
    pos[id]=cnt_list++;
    int i,ip;
    for(i=0;i<nu[id];i++)
    {
        ip=adj[id][i];
        if(!vis[ip])
        {
            pa[ip]=id;
            ps[ip]=ie[id][i];
            dfs(ip);
        }
    }
}
void solve(int id,int pr)
{
    int i,j,s,ip,ns;
    for(i=0;i<nu[id];i++)
    {
        ip=adj[id][i];
        if(ip!=pr&&bel[ie[id][i]]<0)
        {
            ps[ip]=i;
            solve(ip,id);
        }
    }
    for(i=0;i<sz[id];i++)
    {
        ip=belong[id][i];
        if(ip+n==pr)
            continue;
        for(j=0;j<nc[ip];j++)
        {
            if(vec[ip][j]==id)
                continue;
            solve(vec[ip][j],ip+n);
        }
    }
    for(i=0;i<nu[id];i++)
    {
        ip=adj[id][i];
        if(ip!=pr&&bel[ie[id][i]]<0)
        {
            if(dp[ip]==0)
            {
                dp[id]=1;
                g[id]=-1;
                break;
            }
        }
    }  
    for(i=0;i<sz[id];i++)
    {
        ip=belong[id][i];
        if(ip+n==pr)
        {
           ps[id]=i+n;
           continue;
        }
        for(j=0;j<nc[ip];j++)
        {
            if(vec[ip][j]==id)
               break;
        }
        f[i]=0;
        awp[i]=3;
         for(s=j+1;s<j+nc[ip];s++)
        {
            ns=s%nc[ip];
            if((g[vec[ip][ns]]<0||g[vec[ip][ns]]==2||g[vec[ip][ns]]==1)&&dp[vec[ip][ns]]==1)
            {
                if((s-j)%2==0)
                {
                    f[i]=1;
                    if(g[vec[ip][ns]]==2||g[vec[ip][ns]]==1)
                       awp[i]=2;
                    else
                       awp[i]=-1;
                }
                break;
            }
        }
        for(s=j-1;s>j-nc[ip];s--)
        {
            if(s<0)
               ns=s+nc[ip];
            else
               ns=s;
           if((g[vec[ip][ns]]<0||g[vec[ip][ns]]==2||g[vec[ip][ns]]==1)&&dp[vec[ip][ns]]==1)
            {
                if((j-s)%2==0)
                {
                    f[i]=1;
                    if(g[vec[ip][ns]]==2||g[vec[ip][ns]]==1)
                         awp[i]=2;
                    else
                    { 
                       if(awp[i]==3)
                          awp[i]=-1;
                    }
                }
                break;
            }
        }
        if(s<=j-nc[ip])
            awp[i]=nc[ip]%2;
        if(f[i]==1)
        {
            dp[id]=1;
            g[id]=-1; 
        }
        fg[id][i]=f[i];
        ag[id][i]=awp[i];
    }
    if(dp[id]==0)
    {
        int ts=0;
        for(i=0;i<sz[id];i++)
        {
            ip=belong[id][i];
            if(ip+n==pr)
                continue;
             if(awp[i]==2)
             {
                g[id]=2;
                dp[id]=1;
                break;
             }
             if(awp[i]==1)
                 ts^=1;
        }
        if(i>=sz[id])
        {
            dp[id]=ts;
            g[id]=ts;
        }
    }
}
void bfs()
{
    queue[0]=0;
    pm[0]=-1;
    int temp1,temp2,temp,id,i,j,s,p,q,ip,iee,ns,ch,dd,ad;
    temp1=temp2=0;
    temp=1;
    while(temp1<=temp2)
    {
        for(i=temp1;i<=temp2;i++)
        {
            id=queue[i];
            int num[2][2];
            memset(num,0,sizeof(num));
            for(j=0;j<nu[id];j++)
            {
                ip=adj[id][j];
                if(bel[ie[id][j]]<0)
                {
                    if(ip==pm[id])
                    {
                        iee=ps[id];
                        f[j]=dyn[pm[id]][iee]; 
                    }
                    else
                        f[j]=dp[ip];
                    num[0][1-f[j]]++;
                }
            }
            for(j=0;j<sz[id];j++)
            {
                ip=belong[id][j];
                f[j+nu[id]]=fg[id][j];
                awp[j+nu[id]]=ag[id][j];
                num[0][f[j+nu[id]]]++;
                if(awp[j+nu[id]]>=1&&awp[j+nu[id]]<=2)
                    num[1][awp[j+nu[id]]-1]++;
            } 
            if(num[0][1]>0)
                ans[id]=1;
            else if(num[1][1]>0)
                ans[id]=1;
            else
                ans[id]=num[1][0]%2;
            for(j=0;j<nu[id];j++)
            {
                ip=adj[id][j];
                if(bel[ie[id][j]]<0)
                {
                    dd=f[j];
                    num[0][1-dd]--;
                    if(num[0][1]>0)
                    {
                       dyn[id][j]=1;
                       gn[id][j]=-1;
                    }
                    else if(num[1][1]>0)
                    {
                        dyn[id][j]=1;
                        gn[id][j]=2;
                    }
                    else
                        gn[id][j]=dyn[id][j]=num[1][0]%2;
                    num[0][1-dd]++;
                }
            }
            for(j=0;j<sz[id];j++)
            {
                ip=belong[id][j];
                dd=fg[id][j];
                ad=ag[id][j];

                num[0][dd]--;
                if(ad>=1&&ad<=2)
                    num[1][ad-1]--;
                if(num[0][1]>0)
                {
                   dyn[id][j+nu[id]]=1;
                   gn[id][j+nu[id]]=-1;
                }
                else if(num[1][1]>0)
                {
                   dyn[id][j+nu[id]]=1;
                   gn[id][j+nu[id]]=2;
                }
                else
                   gn[id][j+nu[id]]=dyn[id][j+nu[id]]=num[1][0]%2;
                num[0][dd]++;
                if(ad>=1&&ad<=2)
                   num[1][ad-1]++;
            }
            for(j=0;j<sz[id];j++)
            {
                 ip=belong[id][j];
                 if(ip+n==pm[id])
                     continue;
                 ch=-1;
                 for(s=0;s<nc[ip];s++)
                     nxt[0][vec[ip][s]]=nxt[1][vec[ip][s]]=-1;
                 int bwp=-1;
                 for(s=0;s<2*nc[ip];s++)
                 {
                    ns=s%nc[ip];
                     if(nxt[0][vec[ip][ns]]>=0)
                         break;
                     if(ch>=0&&ns!=ch)
                     {
                         nxt[0][vec[ip][ns]]=ch;
                         gs[0][vec[ip][ns]]=bwp;
                     }
                     if(vec[ip][ns]==id)
                     {
                         iee=j;
                         dd=dyn[id][iee+nu[id]];
                         ad=gn[id][iee+nu[id]];
                     }
                     else
                     {
                         dd=dp[vec[ip][ns]];
                         ad=g[vec[ip][ns]];
                     }
                     if((ad<0||ad==1||ad==2)&&dd==1)
                     {
                         bwp=ad;
                         ch=ns;
                     }
                 }
                 ch=-1;
                 for(s=2*nc[ip]-1;s>=0;s--)
                 {
                      ns=s%nc[ip];
                      if(nxt[1][vec[ip][ns]]>=0)
                          break;
                      if(ch>=0&&ns!=ch)
                      {
                          nxt[1][vec[ip][ns]]=ch;
                          gs[1][vec[ip][ns]]=bwp;
                      }
                      if(vec[ip][ns]==id)
                      {
                         iee=j;
                         dd=dyn[id][iee+nu[id]];
                         ad=gn[id][iee+nu[id]];
                      }
                      else
                      {
                          dd=dp[vec[ip][ns]];
                          ad=g[vec[ip][ns]];
                      }
                      if((ad<0||ad==1||ad==2)&&dd==1)
                      {
                         ch=ns;
                         bwp=ad;
                      }
                 }
                 for(s=0;s<nc[ip];s++)
                 {
                     if(vec[ip][s]==id)
                         continue;
                     int ix;
                     iee=ps[vec[ip][s]]-n;
                     fg[vec[ip][s]][iee]=0;
                     ag[vec[ip][s]][iee]=3;
                     if(nxt[0][vec[ip][s]]>=0)
                     {
                        ix=(s-nxt[0][vec[ip][s]])%nc[ip];
                        if(ix<0)
                           ix+=nc[ip];
                        int iq=nxt[0][vec[ip][s]];
                        if(ix%2==0)
                        {
                           fg[vec[ip][s]][iee]=1;
                           if(gs[0][vec[ip][s]]==2||gs[0][vec[ip][s]]==1)
                                ag[vec[ip][s]][iee]=2;   
                           else
                                ag[vec[ip][s]][iee]=-1;
                        }
                        ix=(nxt[1][vec[ip][s]]-s)%nc[ip];
                        if(ix<0)
                            ix+=nc[ip];
                        if(ix%2==0)
                        {
                            fg[vec[ip][s]][iee]=1;
                            if(gs[1][vec[ip][s]]==2||gs[1][vec[ip][s]]==1)
                                ag[vec[ip][s]][iee]=2;   
                            else if(ag[vec[ip][s]][iee]==3)
                                ag[vec[ip][s]][iee]=-1;
                        }
                     }
                     else
                        ag[vec[ip][s]][iee]=nc[ip]%2;
                 }
            }
            for(j=0;j<nu[id];j++)
            {
                ip=adj[id][j];
                if(ip==pm[id]||bel[ie[id][j]]>=0)
                   continue;
                pm[ip]=id;
                queue[temp++]=ip;
            }
            for(j=0;j<sz[id];j++)
            {
                ip=belong[id][j];
                if(ip+n==pm[id])
                    continue;
                for(s=0;s<nc[ip];s++)
                {
                    if(vec[ip][s]==id)
                        continue;
                    pm[vec[ip][s]]=ip+n;
                    queue[temp++]=vec[ip][s];
                }
            }
        }
        temp1=temp2+1;
        temp2=temp-1;
    }
}
int main()
{
    int i,j,s,p,q,a,b;
    read(n);
    read(m);
    memset(nu,0,sizeof(nu));
    for(i=0;i<m;i++)
    {
        read(a);
        read(b);
        a--;
        b--;
        nu[a]++;
        nu[b]++;
        e[i].id1=a;
        e[i].id2=b;
    }
    for(i=0;i<n;i++)
    {
        adj[i]=(int*)malloc(nu[i]*sizeof(int));
        ie[i]=(int*)malloc(nu[i]*sizeof(int));
    }
    memset(nu,0,sizeof(nu));
    for(i=0;i<m;i++)
    {
        a=e[i].id1;
        b=e[i].id2;
        adj[a][nu[a]++]=b;
        adj[b][nu[b]++]=a;
        ie[a][nu[a]-1]=i;
        ie[b][nu[b]-1]=i;
    }
    cnt_list=0;
    memset(vis,false,sizeof(vis));
   memset(g,0,sizeof(g));
    memset(dp,0,sizeof(dp));
    dfs(0);
    num_cir=0;
    memset(bel,-1,sizeof(bel));
    memset(sz,0,sizeof(sz));
    for(i=0;i<m;i++)
    {
        if(pos[e[i].id1]>pos[e[i].id2])
            swap(e[i].id1,e[i].id2);
        if(pa[e[i].id1]==e[i].id2||pa[e[i].id2]==e[i].id1)
            continue;
        cnt_list=0;
        a=e[i].id2;
        bel[i]=num_cir; 
        while(true)
        {
            sz[a]++;
            list[cnt_list++]=a;
            if(a==e[i].id1)
               break;
            bel[ps[a]]=num_cir;
            a=pa[a];
        }
        nc[num_cir]=cnt_list;
        vec[num_cir]=(int*)malloc(cnt_list*sizeof(int));
        for(j=cnt_list-1;j>=0;j--)
            vec[num_cir][j]=list[j];
        num_cir++;
    }
    for(i=0;i<n;i++)
    {
        belong[i]=(int*)malloc(sz[i]*sizeof(int));
        sz[i]=0;
    }
    for(i=0;i<num_cir;i++)
        for(j=0;j<nc[i];j++)
            belong[vec[i][j]][sz[vec[i][j]]++]=i;
    for(i=0;i<n;i++)
    {
        gn[i]=(int*)malloc((nu[i]+sz[i])*sizeof(int));
        dyn[i]=(int*)malloc((nu[i]+sz[i])*sizeof(int));
        fg[i]=(int*)malloc(sz[i]*sizeof(int));
        ag[i]=(int*)malloc(sz[i]*sizeof(int));
        for(j=0;j<nu[i]+sz[i];j++)
            gn[i][j]=dyn[i][j]=0;
        for(j=0;j<sz[i];j++)
        {
            fg[i][j]=0;
            ag[i][j]=0;
        }
    }
    solve(0,-1);
    ans[0]=dp[0];
    bfs();
    for(i=0;i<n;i++)
    {
        if(ans[i])
          puts("1");
        else
          puts("2");
    }
    for(i=0;i<n;i++)
    {
        free(adj[i]);
        free(ie[i]);
        free(dyn[i]);
        free(gn[i]);
        free(fg[i]);
        free(ag[i]);
        free(belong[i]);
    }
    for(i=0;i<num_cir;i++)
        free(vec[i]);
    return 0;
}

#include <ctime>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <cctype>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <iostream>
#include <sstream>
#include <functional>
using namespace std;
char mat[111][111];
int n,deg[111],uk[111][111],now[111],tot;
int pa[111],num[111];
int dist[111];
int adj[111][111];
int vec[111][111],num_vec[111];
int vs[111],times,u;
int spfa()
{
    int id,ip,i,j,s,p,q;
    for(i=0;i<=n;i++)
         num_vec[i]=0;
    for(i=0;i<n;i++)
    {
        dist[i]=now[i]+deg[i]; 
        pa[i]=-1;
        vec[now[i]+deg[i]][num_vec[now[i]+deg[i]]++]=i;
    } 
    times++;
    while(true)
    {
        for(;u>=0;u--)
        {
            while(num_vec[u]>0)
            {
                id=vec[u][num_vec[u]-1];
                if(vs[id]!=times)
                   break;
                num_vec[u]--;
            }
            if(num_vec[u]>0)
                break;
        }
        if(u<0)
           return -1;
        num_vec[u]--;
        vs[id]=times;
        for(j=0;j<num[id];j++)
        {
            ip=adj[id][j];
            if(dist[ip]<dist[id]&&uk[id][ip]==0)
            {
                dist[ip]=dist[id];
                pa[ip]=id;
                if(dist[ip]>=now[ip]+deg[ip]+2)
                    return ip;
                vec[dist[ip]][num_vec[dist[ip]]++]=ip;
            }
        }
    }
}
int main()
{
    int i,j,s,p,q,id,ip,dk;
    while(scanf("%d",&n)==1)
    {
        tot=n*(n-1)*(n-2)/6;
        for(i=0;i<n;i++)
            deg[i]=now[i]=num[i]=0;
        for(i=0;i<n;i++)
          for(j=0;j<n;j++)
          {
             mat[i][j]=getchar();
             while(mat[i][j]<'0'||mat[i][j]>'9')
                 mat[i][j]=getchar();
              if(i==j)
                 continue;
              if(mat[i][j]=='0')
                 deg[i]++;
              else if(mat[i][j]=='2')
              {
                 if(i<j)
                 {
                      uk[i][j]=rand()%2;
                      uk[j][i]=1-uk[i][j]; 
                      if(uk[i][j]==0) 
                         now[i]++;
                      else
                         now[j]++;
                 }
                 adj[i][num[i]++]=j;
              }
          }
        u=n;
        while(true)
        {
             ip=spfa();
             if(ip<0)
                break;
             now[ip]++;
             while(pa[ip]>=0)
             {
                 uk[pa[ip]][ip]=1;
                 uk[ip][pa[ip]]=0;
                 ip=pa[ip];
             }
             now[ip]--;
        }
        for(i=0;i<n;i++)
        {
            dk=deg[i]+now[i];
            tot-=dk*(dk-1)/2;
        }
        printf("%d\n",tot);
        for(i=0;i<n;i++)
        {
           for(j=0;j<n;j++)
           {
               if(mat[i][j]=='2')
                   mat[i][j]=uk[i][j]+'0';
               putchar(mat[i][j]);
               putchar(' ');
           }
           printf("\n");
        }
    }
    return 0;
}

时间复杂度上界是 O(m^2),但是实测结果远远达不到，大概只有 线性，而且 大范围数据仅仅是 输入输出消耗时间