给出一张无向图,要求找出尽量多的长度为2的不同路径(边不可以重复使用,点可以重复使用)
yzy:这是原题 http://www.lydsy.com/JudgeOnline/problem.php?id=4874 首先猜测,一个连通块内,如果是偶数条边,那么所有边都可以用上.如果是奇数条边,那么只会剩下一条边.只要给出一个方案构造的方法,那么正确性就可以从构造方法中得出. 长度为2的路径中中间那个点和两条边都有关.我们可以认为这两条边都属于中间那个点. 于是现在就变成把每条边分配给它的两个端点中的一个.显然,一个连通块最多只能有一个端点被分配奇数条边.
构造方法是这样的:从连通块里拎出一棵生成树,然后把非树边随便分配,接下来从叶节点往上,依次分配所有非树边,从下到上依次确保每个点都被分配了偶数条边.最后除了根节点之外的点一定都被分配了偶数条边,根节点被分配的边数奇偶性和连通块内总边数的奇偶性相同.
#include <cstdio> #include <vector> using namespace std; const int maxn=200005; struct edge{ int to,next,num; }lst[maxn<<1];int len=1,first[maxn]; void addedge(int a,int b,int w){ lst[len].to=b;lst[len].next=first[a];lst[len].num=w; first[a]=len++; } int u[maxn],v[maxn],typ[maxn];//typ[i]==0 belong to u[i] int sum[maxn]; int ufs[maxn]; int find(int x){ return x==ufs[x]?x:ufs[x]=find(ufs[x]); } bool ontree[maxn]; void dfs(int x,int p){ for(int pt=first[x];pt;pt=lst[pt].next){ if(lst[pt].to!=p){ dfs(lst[pt].to,x); if(sum[lst[pt].to]==0){ typ[lst[pt].num]=(v[lst[pt].num]==x); sum[x]^=1; }else{ typ[lst[pt].num]=(u[lst[pt].num]==x); sum[lst[pt].to]=0; } } } } vector<int> P[maxn]; int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=m;++i)scanf("%d%d",u+i,v+i); for(int i=1;i<=n;++i)ufs[i]=i; for(int i=1;i<=m;++i){ if(find(u[i])==find(v[i])){ typ[i]=0;sum[u[i]]^=1; }else{ ufs[find(u[i])]=find(v[i]); addedge(u[i],v[i],i);addedge(v[i],u[i],i); } } for(int i=1;i<=n;++i){ if(ufs[i]==i)dfs(i,0); } for(int i=1;i<=m;++i){ if(typ[i]==0)P[u[i]].push_back(v[i]); else P[v[i]].push_back(u[i]); } int ans=0; for(int i=1;i<=n;++i){ ans=ans+P[i].size()/2; } printf("%d\n",ans); for(int i=1;i<=n;++i){ int sz=P[i].size(); for(int j=0;j+1<sz;j+=2){ printf("%d %d %d\n",P[i][j],i,P[i][j+1]); } } return 0; }转载于:https://www.cnblogs.com/liu-runda/p/7542312.html
