给出一张有向图,更改其中一些边的方向,最大化出度等于入度的点的个数。
如果所有点出度等于入度,那么这张图构成欧拉回路。
于是我们连接图中的奇点,使原图成为欧拉回路。
然后遍历这个图,确定每条边的方向,奇点的边显然不对答案造成影响。
Ps:这题出题人心态不对,时限卡的非常猥琐。
#includeusing namespace std; const int maxn=100005,maxm=800005; char nc(){ static char buf[100000],*l=buf,*r=buf; if (l==r) r=(l=buf)+fread(buf,1,100000,stdin); if (l==r) return EOF;return *l++; } inline int _read(){ int num=0;char ch=nc(); while(ch<'0'||ch>'9') ch=nc(); while(ch>='0'&&ch<='9') num=num*10+ch-48,ch=nc(); return num; } struct jz{ int x,y; }a[maxm]; int n,m,ans[maxm],f[maxn],b[maxn]; int tot,sum,lnk[maxn],nxt[maxm],son[maxm]; bool vis[maxn]; inline void add(int x,int y){nxt[++sum]=lnk[x];lnk[x]=sum;son[sum]=y;} void DFS(int x){ vis[x]=1; for (int j=lnk[x];j;j=nxt[j]) if (!ans[son[j]]){ if (x==a[son[j]].x) ans[son[j]]=1,DFS(a[son[j]].y); else ans[son[j]]=2,DFS(a[son[j]].x); } } int main(){ freopen("exam.in","r",stdin); freopen("exam.out","w",stdout); n=_read();m=_read(); for (int i=1;i<=m;i++){ int x=_read(),y=_read(); f[x]++;f[y]++; a[++tot].x=x;a[tot].y=y; add(x,tot);add(y,tot); } for (int i=1;i<=n;i++) if (f[i]%2==1) b[++b[0]]=i; for (int i=1;i<=b[0]/2;i++) a[++tot].x=b[i*2-1],a[tot].y=b[i*2],add(b[i*2-1],tot),add(b[i*2],tot); for (int i=1;i<=n;i++) if (!vis[i]) DFS(i); printf("%d\n",n-b[0]); for (int i=1;i<=m;i++) if (ans[i]==1) putchar('0');else putchar('1'); return 0; }