首页 > 代码库 > Codeforces Round #375 (Div. 2)E. One-Way Reform

Codeforces Round #375 (Div. 2)E. One-Way Reform

2024-08-15 15:31:04   219人阅读

题目链接：传送门

题目大意：一副无向图，要求你给边定向（变为有向图），使出度等于入度的点最多，输出有多少

　　　　　个点，并且输出定向后的边（前为起点，后为终点）

题目思路：欧拉路

　　　　　我们这样考虑，先考虑无向图的点的度数，如果为奇数则一定无法变为题目要求的点，ans-1

　　　　　对于度为偶数的点则一定可以通过调整满足。

处理方法：新建一个虚拟节点0，使所有度为奇数的点向其连一条边，那么最终图中的点的度数都为偶数。

　　　　　这样就满足欧拉路的条件了。我们只需要跑欧拉路并且将走过的路径保留下来即可。

　　　　　注意将与虚拟节点连的边删去。

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue>10 #include <string>11 #include <vector>12 #include <set>13 #include <map>14 #include <climits>15 #define lson rt<<1,l,mid16 #define rson rt<<1|1,mid+1,r17 #define fi first18 #define se second19 #define ping(x,y) ((x-y)*(x-y))20 #define mst(x,y) memset(x,y,sizeof(x))21 #define mcp(x,y) memcpy(x,y,sizeof(y))22 using namespace std;23 #define gamma 0.577215664901532860606512024 #define MOD 100000000725 #define inf 0x3f3f3f3f26 #define N 5000527 #define maxn 3001028 typedef pair<int,int> PII;29 typedef long long LL;30 LL read(){31     LL x=0,f=1;char ch=getchar();32     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}33     while(ch>=‘0‘&&ch<=‘9‘){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}34     return x*f;35 }36 37 int n,m,k,ans,in[205];38 int vis[205][205];39 set<int>S[205];40 vector<PII >V;41 void dfs(int u){42     while(S[u].size()){43         int x=*S[u].begin();S[u].erase(S[u].begin());44         if(vis[u][x])continue;45         vis[u][x]=vis[x][u]=1;46         V.push_back(make_pair(u,x));47         dfs(x);48     }49 }50 int main(){51     int i,j,group,x,y,v,Case=0;52     group=read();53     while(group--){54         n=read(),m=read();55         mst(in,0);V.clear();56         mst(vis,0);57         for(i=0;i<=n;++i) S[i].clear();58         for(i=1;i<=m;++i){59             x=read(),y=read();60             S[x].insert(y),S[y].insert(x);61             ++in[x],++in[y];62         }63         int ans=n;64         for(i=1;i<=n;++i)if(in[i]&1){65             --ans;66             S[0].insert(i),S[i].insert(0);67         }68         for(i=1;i<=n;++i)69             if(S[i].size())70                 dfs(i);71         printf("%d\n",ans);72         for(PII u:V)if(u.fi!=0&&u.se!=0){73             printf("%d %d\n",u.fi,u.se);74         }75     }76     return 0;77 }

 

Codeforces Round #375 (Div. 2)E. One-Way Reform


联系
我们