【NOIP2017提高A组模拟10.10】Graph

Description

给定一张n个点m条边的无向图，每条边连接两个顶点，保证无重边自环，不保证连通
你想在这张图上进行若干次旅游，每次旅游可以任选一个点x作为起点，再走到一个与x 直接有边相连的点y，再走到一个与y 直接有边相连的点z 并结束本次旅游
作为一个旅游爱好者，你不希望经过任意一条边超过一次，注意一条边不能即正向走一次又反向走一次，注意点可以经过多次，在满足此条件下，你希望进行尽可能多次的旅游，请计算出最多能进行的旅游次数并输出任意一种方案

Input

第1 行两个正整数n 与m，表示全图的点数与边数
下接m 行，每行两个数字u 与v 表示一条边

Output

第1 行一个整数cnt 表示答案
下接cnt 行，每行三个数字x, y 与z，表示一次旅游的路线
如有多种旅行方案，任意输出一种即可

Sample Input

4 5
1 2
3 2
2 4
3 4
4 1

Sample Output

1
2

Solution

对于每个联通块分开考虑
对于每个联通块，答案肯定是边数/2
怎么构造出来呢？
构造出一个生成树
对于每个点，优先匹配返祖边和儿子边，父亲边如果没有可以匹配的就不匹配，留给父亲来匹配那条边
这样一定是最优的

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 1010000
using namespace std;
int n,m,last[N],next[N*10],to[N*10],tot=1,bz[N],ans=0,a[N][3],b[N],c[N],bb[N*10];
void putin(int x,int y)
{
next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
int dg(int x,int fa)
{
bz[x]=1;int j=0,k=0;
for(int i=last[x];i;i=next[i])
if(!b[i]&&!b[i^1])
{
int y=to[i],jy=1;
if(y==fa)
{
j=i;
continue;
}
if(!bz[y]) jy=dg(y,x);
if(jy)
{
if(ans==1300)
{
printf("");
printf("");
}
if(c[0]==0) c[++c[0]]=++ans;
if(k!=0) a[k][2]=i,k=0;else a[c[c[0]]][0]=i,bb[c[c[0]]]=0,a[ans][1]=x,k=c[c[0]],c[0]--;
b[i]=1;
}
}
if(k!=0) if(j!=0) a[k][2]=j,b[j]=1,j=0;else j=1,b[a[k][0]]=0,c[++c[0]]=k,j=1,bb[k]=1;
return j;
}
int main()
{
freopen("graph.in","r",stdin);
freopen("graph.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,1,m)
{
int x,y;scanf("%d%d",&x,&y);
putin(x,y);putin(y,x);
}
a[ans][2]=-1;
fo(i,1,n)
if(!bz[i]) dg(i,0);
printf("%dn",ans-c[0]);
fo(i,1,ans) if(!bb[i]) printf("%d %d %dn",to[a[i][0]],a[i][1],to[a[i][2]]);
}

最后

以上就是坚定悟空为你收集整理的【NOIP2017提高A组模拟10.10】Graph的全部内容，希望文章能够帮你解决【NOIP2017提高A组模拟10.10】Graph所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。