题意

给你一个无向图，每条边只能用一次，问你最多可以组成多少个三元组，并输出其中一个方案

题解

这题比较神。。
昨晚想了很久都没弄出来。。
其实是太困了。。基本上无法思考

怎么做呢。。
我们对于每个联通块弄出一个生成树。。
然后对于非树边随意地表向
对于一个点，每两条指向他的边就可以成为一个三元组
然后在这里表向完毕后，我们可以知道每个点的入度
就从叶子开始网上扫
如果入度是偶数，就把他和他父亲的边指向父亲
否则指向自己

可以知道，在每一个联通块中我们浪费的只有当边为奇数时浪费一条，达到答案的最大值，因此该做法是最优的

#include<cstdio>
#include<cstdlib>
#include<cstring>
const int N=200005*2;
int n,m;
struct qq
{int x,y;int last;
}e[N];int num=0,last[N];
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
int f[N];
bool vis[N];
int find (int x)
{return f[x]==x?f[x]:f[x]=find(f[x]);
}
bool ok[N];//这条边有没有用过
int du[N];//这个点的入度
bool shen[N];//这个点处理过没有
int ans=0;
qq s[N];int num1,last1[N];
void Init (int x,int y)
{num1++;s[num1].x=x;s[num1].y=y;s[num1].last=last1[x];last1[x]=num1;
}
void dfs (int x,int fa)
{for (int u=last[x];u!=-1;u=e[u].last){if (ok[u]==false) continue;//这是一条非树边，不管他int y=e[u].y;if (y==fa) continue;dfs(y,x);if (du[y]%2==1) {du[y]++;Init(y,x);}else {du[x]++;Init(x,y);}}
}
void prepare ()
{memset(ok,false,sizeof(ok));for (int u=1;u<=n;u++)f[u]=u;for (int u=1;u<=num;u+=2){int x=e[u].x,y=e[u].y;int fx=find(x),fy=find(y);if (fx==fy) continue;f[fx]=fy;ok[u]=ok[u+1]=true;}for (int u=1;u<=num;u+=2){if (ok[u]) continue;Init(e[u].y,e[u].x);du[e[u].y]++;}memset(shen,false,sizeof(shen));for (int u=1;u<=n;u++){int fx=find(u);if (shen[fx]==true) continue;shen[fx]=true;dfs(fx,0);}
}
int main()
{num1=0;memset(last1,-1,sizeof(last1));num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);for (int u=1;u<=m;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}prepare();/*for (int u=1;u<=num1;u++) printf("%d %d %d\n",s[u].x,s[u].y,s[u].last);system("pause");*/for (int u=1;u<=n;u++) ans=ans+du[u]/2;printf("%d\n",ans);for (int u=1;u<=n;u++){int X=-1;for (int i=last1[u];i!=-1;i=s[i].last){/* printf("%d %d %d %d\n",i,s[i].x,s[i].y,s[i].last);system("pause");*/int y=s[i].y;if (X==-1) X=y;else{printf("%d %d %d\n",X,u,y);X=-1;}}}return 0;
}