• One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There arencities andmtwo-way roads in Berland, e...


One-Way Reform

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.
The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

Input

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.
Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.
The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.
It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.
Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

Output

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.
In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

Example

input

25 52 14 52 31 33 57 23 74 2

output

31 33 55 43 22 132 43 7分析：对于度数为奇数的节点，必然存在一条子欧拉路径，那么除去两个端点，其他的都是对答案有贡献的；　　　然后对于子欧拉回路，每个节点都有贡献；　　　为了防止重复计数，vis数组判断有没有访问过；代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, ls[rt]
#define Rson mid+1, R, rs[rt]
const int maxn=2e2+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
{
ll x=0;int f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,k,t,now[maxn],du[maxn],cnt,ret;
bool c[maxn][maxn],vis[maxn];
vector<pii>ans;
void dfs(int p)
{
if(!vis[p])vis[p]=true,cnt++;
for(;now[p]<=n;now[p]++)
{
int q=now[p];
if(c[p][q])
{
ans.pb(mp(p,q));
--du[p],--du[q];
c[p][q]=c[q][p]=false;
dfs(q);
break;
}
}
}
int main()
{
int i,j;
scanf("%d",&t);
while(t--)
{
ans.clear();
ret=0;
memset(now,0,sizeof(now));
memset(vis,false,sizeof(vis));
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&j,&k);
du[j]++,du[k]++;
c[j][k]=c[k][j]=true;
}
for(i=1;i<=n;i++)
{
if(du[i]&1)
{
cnt=0;
dfs(i);
ret+=cnt-2;
}
}
for(i=1;i<=n;i++)
{
if(du[i])
{
cnt=0;
dfs(i);
ret+=cnt;
}
else if(!du[i]&&!vis[i])ret++;
}
printf("%d\n",ret);
for(pii x:ans)printf("%d %d\n",x.fi,x.se);
}
//system("Pause");
return 0;
}

转载于:https://www.cnblogs.com/dyzll/p/5929980.html
展开全文 • One-Way Reform Description There arencities andmtwo-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of citie...


One-Way Reform
Description

There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.
The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

Input

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.
Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.
The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.
It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.
Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

Output

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.
In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

Sample Input

Input

25 52 14 52 31 33 57 23 74 2

Output

31 33 55 43 22 132 43 7题意是给出一个无向图，求如何将该无向图变成有向图后使得出度等于入度的点最多，我们可以把新开一个节点，把度数为奇数的点连接到新节点上，然后求欧拉回路，由于这道题不需要输出路径，所以可以枚举每个点让这个点搜索到最深就能得到需要的图。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
int deg[maxn];
vector<int> g[maxn];
int vis[maxn];
void AddEdge(int u, int v) {
g[u].emplace_back(v);
deg[u]++;
}
int it[maxn];
set< pair<int, int> > st;

void dfs(int x) {
while(it[x]<g[x].size()) {
int v=g[x][it[x]];
it[x]++;
if(st.count({v,x})==1)continue;
st.insert({x,v});
dfs(v);
}
}

int main() {
int t;
scanf("%d", &t);
while(t--) {
st.clear();
memset(it, 0, sizeof(it));
memset(vis, 0, sizeof(vis));
memset(deg, 0, sizeof(deg));
for(int i = 0; i < maxn; i++) g[i].clear();
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
}
int ans = n;
for(int i = 1; i <= n; i++) {
//printf("check %d %d\n", i, deg[i]);
if(deg[i] % 2 != 0) {
ans--;
}
}
for(int i = 1; i <= n; i++) {
if(!it[i]) dfs(i);
}
printf("%d\n", ans);
for(auto x:st) {
if(x.first && x.second) {
printf("%d %d\n", x.first, x.second);
}
}
}
}

转载于:https://www.cnblogs.com/lonewanderer/p/5936275.html
展开全文 • One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n cities and m two-way roads in


One-Way Reform

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.
The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

Input

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.
Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.
The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.
It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.
Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

Output

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.
In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

Example

input

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

output

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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
using namespace std;
const int N = 210;
set<int>q[N];
typedef pair<int,int>node;
vector<node>ans;
void dfs(int x)
{
while(q[x].size())
{
int u=*q[x].begin();
q[x].erase(u), q[u].erase(x);
ans.push_back(make_pair(x,u));
dfs(u);
}
}

int main()
{
int t;
scanf("%d", &t);
while(t--)
{

ans.clear();
int n, m;
scanf("%d %d", &n, &m);
for(int i=0;i<=n;i++)
q[i].clear();
for(int i=0;i<m;i++)
{
int x, y;
scanf("%d %d", &x, &y);
q[x].insert(y);
q[y].insert(x);
}
for(int i=1;i<=n;i++)
{
if(q[i].size()%2==1)
{
q[n+1].insert(i);
q[i].insert(n+1);
}
}
printf("%d\n",n-q[n+1].size());
for(int i=1;i<=n;i++)
{
dfs(i);
}
for(int i=0;i<ans.size();i++)
{
if(ans[i].first!=n+1&&ans[i].second!=n+1)
{
printf("%d %d\n",ans[i].first,ans[i].second);
}
}
}
return 0;
}

参考：题意给你一个无向图，然后让你给边定向，使得入度等于出度的点最多。题解：考虑欧拉图，只要所有点的度数为偶数就可以了。那么答案就是奇数度数的点集，然后我们不停的dfs，把欧拉路都画出来就行了。代码#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
set<int>s[maxn];
vector<pair<int,int> >ans;
int n,m;
void dfs(int x)
{
while(s[x].size())
{
int p=*s[x].begin();
s[x].erase(p),s[p].erase(x);
ans.push_back(make_pair(x,p));
dfs(p);
}
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
ans.clear();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x,y;scanf("%d%d",&x,&y);
s[x].insert(y);
s[y].insert(x);
}
for(int i=1;i<=n;i++)
{
if(s[i].size()%2==1)
s[n+1].insert(i),s[i].insert(n+1);
}
cout<<n-s[n+1].size()<<endl;
for(int i=1;i<=n;i++)
dfs(i);
for(int i=0;i<ans.size();i++)
if(ans[i].first!=n+1&&ans[i].second!=n+1)
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
}


展开全文 • 题目连接：http://codeforces.com/contest/723/problem/E ...E. One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input outp
题目连接：http://codeforces.com/contest/723/problem/E

E. One-Way Reform

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more than one road connecting each pair of cities, and there is no road which connects the city with itself. It is possible that there is no way to get from one city to some other city using only these roads.
The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number of roads that begins in the city equals to the number of roads that ends in it.

Input

The first line contains a positive integer t (1 ≤ t ≤ 200) — the number of testsets in the input.
Each of the testsets is given in the following way. The first line contains two integers n and m (1 ≤ n ≤ 200, 0 ≤ m ≤ n·(n - 1) / 2) — the number of cities and the number of roads in Berland.
The next m lines contain the description of roads in Berland. Each line contains two integers u and v (1 ≤ u, v ≤ n) — the cities the corresponding road connects. It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities.
It is guaranteed that the total number of cities in all testset of input data doesn't exceed 200.
Pay attention that for hacks, you can only use tests consisting of one testset, so t should be equal to one.

Output

For each testset print the maximum number of such cities that the number of roads that begins in the city, is equal to the number of roads that ends in it.
In the next m lines print oriented roads. First print the number of the city where the road begins and then the number of the city where the road ends. If there are several answers, print any of them. It is allowed to print roads in each test in arbitrary order. Each road should be printed exactly once.

Example

input

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

output

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

题目大意：给你一个无向图，然后让你给边定向，使得入度等于出度的点最多。

解题思路：构造出第n+1个点，把度数为奇数的点把一条边连去n+1的点，那么剩下的边就能构造出一条欧拉回路出来。答案其实就是度数为偶数的点的集合。

/* ***********************************************
┆  ┏┓　　　┏┓ ┆
┆┏┛┻━━━┛┻┓ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　━　　　┃ ┆
┆┃　┳┛　┗┳　┃ ┆
┆┃　　　　　　　┃ ┆
┆┃　　　┻　　　┃ ┆
┆┗━┓　马　┏━┛ ┆
┆　　┃　勒　┃　　┆
┆　　┃　戈　┗━━━┓ ┆
┆　　┃　壁　　　　　┣┓┆
┆　　┃　的草泥马　　┏┛┆
┆　　┗┓┓┏━┳┓┏┛ ┆
┆　　　┃┫┫　┃┫┫ ┆
┆　　　┗┻┛　┗┻┛ ┆
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <bitset>
using namespace std;

#define rep(i,a,b) for (int i=(a),_ed=(b);i<=_ed;i++)
#define per(i,a,b) for (int i=(b),_ed=(a);i>=_ed;i--)
#define pb push_back
#define mp make_pair
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define mod 1000000007
#define LL long long
#define ULL unsigned long long
#define MS0(X) memset((X), 0, sizeof((X)))
#define SelfType int
SelfType Gcd(SelfType p,SelfType q){return q==0?p:Gcd(q,p%q);}
SelfType Pow(SelfType p,SelfType q){SelfType ans=1;while(q){if(q&1)ans=ans*p;p=p*p;q>>=1;}return ans;}
#define Sd(X) int (X); scanf("%d", &X)
#define Sdd(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define Sddd(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define reunique(v) v.resize(std::unique(v.begin(), v.end()) - v.begin())
#define all(a) a.begin(), a.end()
#define   mem(x,v)      memset(x,v,sizeof(x))
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;}

const int N = 205;
set<int>s[N];
int n,m;

void dfs(int x)
{
while(s[x].size())
{
int p = *s[x].begin();
if(p!=n+1 && x!=n+1)
cout<<x<<" "<<p<<endl;
s[x].erase(p);
s[p].erase(x);
dfs(p);
}
}

int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//ios::sync_with_stdio(0);
//cin.tie(0);
while(t--)
{
for(int i=1;i<=n+1;i++)
s[i].clear();
for(int i=1;i<=m;i++)
{
s[u].insert(v);
s[v].insert(u);
}
for(int i=1;i<=n;i++)
{
if(s[i].size()&1)
{
s[n+1].insert(i);
s[i].insert(n+1);
}
}
cout<<n - s[n+1].size()<<endl;
for(int i=1;i<=n;i++)
dfs(i);
}
return 0;
}



展开全文 • The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number...
• The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the number ... codeforces
• One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n cities and m two-way roads
• One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n cities and m two-way roads in Berland, each r...
• One-Way Reform 题目连接： http://codeforces.com/contest/723/problem/E Description There are n cities and m two-way roads in Berland, each road connects two cities. It is known that there is no more ...
• One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n cities and m two-way
• It's guaranteed that there are no self-loops and multiple roads. It is possible that there is no way along roads between a pair of cities. It is guaranteed that the total number of cities in all... Codeforces C++ c语言 算法
• One-Way Reform time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output There are n cities and m two-way ...
• The road minister decided to make a reform in Berland and to orient all roads in the country, i.e. to make each road one-way. The minister wants to maximize the number of cities, for which the ...
• The family-planning change seemed one of the easier wins in the leadership's 20-page reform blueprint. After decades of marked state interference in the economy, the program suggested a shift, ...
• change, they are "reformed" so that the reform. may not only harm the interests of the student population, but ...
• Measures for Management of Self-service Score Inquiry and Printing Terminalfor Undergraduate Students of Southwest Petroleum University西南石大教 64号XNSDJ No. 64第一条根据学校《关于全面...
• ## 面试

2010-03-10 19:01:00
self-introductionI regard myself as an open-minded person, who can communicate with other people very well. What’s more, I had been the group leader in project team for several times. I can not only training jobs branch
• 1. 自我介绍(self-introduce)Good morning. I am glad to be here for this interview. First let me introduce myself. My name is ***, 24. I come from ******,the capital of *******Province. I graduated from...
• ## 英文自我介绍

千次阅读 2013-11-15 11:56:53
1. 自我介绍(self-introduce) Good morning. I am glad to be here for this interview. First let me introduce myself. My name is ***, 24. I come from ******,the capital of *******Province. I graduated ...
• a daunting task 任重道远 ----------22--------- embraces initiatives reform open-up boost IOC enthusiasm assign state artlessness ratio sincerity reunification convictive IOC Evaluation Commission ...
• 四级仔细阅读同义替换 ...own perception(自己的感知)==self-perception(自我感知) image impacts one’s workplace success(形象影响一个人的工作成功)==image matter to earnings and the indicators of succ
• 1. 自我介绍(self-introduce) Good morning. I am glad to be here for this interview. First let me introducemyself. My name is ***, 24. I come from ******,the capital of *******Province.I graduated styles command exchange features
• ## 2-10

2017-03-28 23:23:29
His positions on health care, tax reform, and financial regulation are of greatest appeal to the super-wealthy. How he intends to improve the situation of the middle class remains obscure. A report ...
• Some 580,000 Cubans, about 12% of the workforce, are “self-employed” in the liberated professions. They have lifted the economy, not least by catering to tourists flocking to the island. But Cuba’... 经济学人 economist
• DPIProceedings.PDF2018 2nd International Conference on Advanced Education and Management Science (AEMS 2018)ISBN: 978-1-60595-604-6Autonomy Support Teaching: Teaching Reform of Bas...
• 每天十个单词，本博客收集整理自《考研英语词汇》，仅供学习和个人积累。 新东方单词在线阅读地址 ，希望这个链接一直都有效 :) 2017年05月16日 22:28:38 recipe词义： n....诀窍，方法 例句： For those who need ...
• waste pollution 乱 扔（垃圾）：litter 生活垃圾 ：domestic garbage 社会习惯：Social habits 促进改革 ：promote reform 有毒物质 ：toxic substance 工业化 ：industrialization 这个项目需要付出巨大的努力...  ...