首页 > 代码库 > poj3387[NEERC2006]IdealFrame
poj3387[NEERC2006]IdealFrame
其实只是把别人的题解强行扩写了
写这篇题解之前我不会的预备知识：
欧拉通路：从图中一个点出发不重复地遍历所有边的路径（可以停在另一个点）
欧拉回路：从图中一个点出发不重复地遍历所有边的回路（必须回到出发点）
欧拉图:存在欧拉回路的图。判断无向图为欧拉图的充要条件是所有点的度数均为偶数。
半欧拉图:存在欧拉通路的图。判断无向图为欧拉图的充要条件是所有点的度数均为偶数或只有两个点的度数为奇数。
一个图中如果存在度数为奇数的点，那么这样的点一定有偶数个。
从一些简单的例子考虑到复杂的例子。
- 给定的图是一个环,答案为0
- 给定的图是一个欧拉图,那么我们只需要把其中的边按照欧拉回路展开即可，答案为度数大于2的点的个数。因为最后的环中所有点的度数均为2，所以度数大于2的点必须被熔断，而且存在只熔断度数大于2的点的方案使得欧拉回路展开成一个环。
例如左边”8”字形的图:从中间度数为4的点中间上下分开即可,得到右图，紫色节点为被熔断的节点形成的新节点。
3.给定的图是一个连通图但不是欧拉图。那么这个图中一定包含偶数个奇度点。因此我们可以将奇度点两两“配对”，每一对点之间连一条“边”，这样就把原图变成了一个所有点度数均为偶的欧拉图，可以将其展开成一个环。这个地方比较难以理解，因为原题没有加边操作，那么怎么连“边”呢？关键在于：虽然我们认为先“加边”再“展开”，但真正操作时，需要先进行熔断操作，再进行连接操作，因为一个度数大于1的点无法进行连接操作。因此连“边”对应到题中的操作，是将两个奇度点进行熔断后再将它们各自产生的一个度数为1的节点连接起来。计算答案的时候，首先统计出原图中奇度点数目和偶度点数目，需要花费奇度点数/2的花费将图转化成欧拉图。再统计出“连边”后图中有多少点的度数大于2。只需用总的点数减去最后度数为2的点数。注意原先度数为1 的点“连边”后会变成度数为2的点。
接下来考虑多个连通块。
4.给定的图不是一个连通图，但每个连通块都是一条链。首尾相接即可，答案=链数
5.给定的图不是一个连通图，但每个连通块都是一个环。每个环熔断一次拆成链再首尾相接，答案=链数×2
6. 给定的图不是一个连通图，每个连通块是一个欧拉图但不是环。我们是否需要先通过几次熔断把欧拉回路展开成环，然后再把环用一次熔断拆成链？不需要。事实上我们在把欧拉回路展开成环的过程中可以“顺手”把环拆成链。还是上面那个8字形的图，我们可以通过一步熔断完成“拆欧拉回路为环”和“拆环为链”。因此，如果一个欧拉回路不是环，那么在把它展开成环的过程中我们就可以完成“拆环为链”，不需要额外熔断一次。对于更加复杂的图，也是这样的。只有本来就是一个环的图才需要单独一次熔断“拆环为链”。
7.多个连通块，每个连通块没有特殊性质（即原题）。
我们希望将每个连通块都变成链，然后把每个链首尾相接即可。那么首先统计连接所有链的花费，把答案加上连通块数目。
然后我们算出每个连通块拆成链的最小费用。实质上我们需要把每个连通块变成半欧拉图（有一条欧拉通路的图）再展开。将半欧拉图展开成一条链的花费和将欧拉图展开成一个环的花费可以相似地计算，等于度数大于2的点数。接下来按照奇度点的个数讨论。
如果一个连通块的奇度点个数恰好为2，我们就可以直接计算展开成链的费用了。
如果奇度点个数大于2，我们需要用之前把“一些相关联的熔断和连接操作”等效为“加边”的思路，将奇度点的个数减少到2，并统计“加边”所需的连接次数（熔断次数不在这里统计）。加完“边”，就可以统计展开成链的费用了。
如果奇度点个数为0（是一个欧拉图），我们可以按照6计算这个连通块的费用。
然而考试写代码的时候并没有完全想清楚上面这些性质…..所以我写成了一大坨的分类讨论和手动枚举情况，还记录每个连通块中度数为1,2,3,4的点的个数，最后没有搞出“拆环为链”有时可以不用额外花费的性质，再加上一堆莫名其妙的细节错误，只有70...如果搞清楚上面这些性质，应该代码不会这样恶心。这个代码是考试代码基础上改的，不建议看，只是让读题解的你感受一下不想透性质就写代码会导致什么后果->_->
#include<cstdio> const int maxn=1005,maxm=50005; int u[maxm],v[maxm]; int ufs[maxn+maxm*2]; int tot=0; int deg[maxn+maxm*2]; int find(int x){ return x==ufs[x]?x:ufs[x]=find(ufs[x]); } void link(int a,int b){ ufs[find(a)]=find(b); } int odd[maxn+maxm*2],even[maxn+maxm*2],one[maxn+maxm*2],two[maxn+maxm*2],three[maxn+maxm*2],four[maxn+maxm*2]; int scc[maxn+maxm*2];int cnt; int maxdeg[maxn+maxm*2]; int main(){ // freopen("frame.in","r",stdin); int n,m;scanf("%d%d",&n,&m); tot=n; for(int i=1;i<=m;++i){ scanf("%d%d",u+i,v+i); if(u[i]==0)u[i]=++tot; if(v[i]==0)v[i]=++tot; deg[u[i]]++;deg[v[i]]++; } for(int i=1;i<=tot;++i)ufs[i]=i; for(int i=1;i<=m;++i){ if(find(u[i])!=find(v[i]))link(u[i],v[i]); } for(int i=1;i<=tot;++i){ if(deg[i]!=0){ if(deg[i]&1)odd[find(i)]++; else even[find(i)]++; if(deg[i]==1)one[find(i)]++; else if(deg[i]==2)two[find(i)]++; else if(deg[i]==3)three[find(i)]++; else if(deg[i]==4)four[find(i)]++; } } for(int i=1;i<=tot;++i){ if(ufs[i]==i&°[i]!=0){ scc[++cnt]=i; } }/* for(int i=1;i<=tot;++i){ if(find(i)==scc[4])printf("%d\n",i); }*/ // printf("%d\n",cnt); if(cnt==1){ int x=scc[1]; two[x]+=one[x]; even[x]+=odd[x]; int ans=odd[x]/2+(even[x]-two[x]); printf("%d\n",ans); }else{ int toteven=0,tottwo=0; int ans=0,x; for(int i=1;i<=cnt;++i){ x=scc[i];//printf("%4d %4d %4d %4d %4d %4d ",odd[x],even[x],one[x],two[x],three[x],four[x]); if(odd[x]==0){ if(four[x]!=0){ two[x]++;odd[x]=one[x]=2; four[x]--; } else if(two[x]!=0){ two[x]--;even[x]--; one[x]=odd[x]=2; }else{ odd[x]=one[x]=2; } ans++; tottwo+=two[x]; toteven+=even[x]; }else{//竟然还有可能拆偶点... if(one[x]>=2){//不需要再拆1了 odd[x]-=2; one[x]-=2; two[x]+=one[x]; ans+=odd[x]/2; }else if(one[x]==1){//再拆一个1 if(three[x]!=0){ three[x]--;ans++; two[x]++; odd[x]-=2; even[x]++; ans+=odd[x]/2; }else{//这里是拆奇点，能否拆偶点？ odd[x]-=2; even[x]++; ans++; ans+=odd[x]/2; } }else if(one[x]==0){//拆出两个1 int g1=0x7f7f7f7f,g2=0x7f7f7f7f,g3=0x7f7f7f7f,g4=0x7f7f7f7f,g5=0x7f7f7f7f; if(three[x]>=2){//拆两个3 g1=2+(odd[x]-2)/2; } if(two[x]!=0){ g2=1+odd[x]/2; } if(four[x]!=0){ g3=odd[x]/2-1; } if(three[x]!=odd[x]&&three[x]!=0){ g4=1+(odd[x]-2)/2; } if(three[x]==0){ g5=2+(odd[x]-2)/2; } if(g1<=g2&&g1<=g3&&g1<=g4&&g1<=g5){ ans+=2; odd[x]-=2;even[x]+=2;two[x]+=2; ans+=(odd[x]/2); }else if(g2<=g1&&g2<=g3&&g2<=g4&&g2<=g5){ ans+=1; two[x]--;even[x]--; ans+=odd[x]/2; }else if(g3<=g1&&g3<=g2&&g3<=g4&&g3<=g5){ two[x]++;//ans+=1; ans+=odd[x]/2; }else if(g4<=g1&&g4<=g2&&g4<=g3&&g4<=g5){ two[x]++;even[x]+=2;//ans+=2; odd[x]-=2; ans+=odd[x]/2; }else{//printf("!"); even[x]+=2;//ans+=2; odd[x]-=2; ans+=odd[x]/2; } } tottwo+=two[x]; toteven+=even[x]+odd[x]; }//printf("ansnow %d\n",ans); } ans+=(toteven-tottwo);ans+=cnt; // printf("%d %d\n",toteven,tottwo); printf("%d\n",ans); }//while(1); return 0; }
poj3387[NEERC2006]IdealFrame