【codeforces 732F】Tourist Reform
2024-09-08 06:07:02
【题目链接】:http://codeforces.com/contest/732/problem/F
【题意】
给你一张无向图;
n个点,m条边;
让你把这张图改成有向边
然后定义r[i]为每个点能够到达的其他点的数目;
让你使得最小的r[i]尽可能地大;
让你输出这个尽可能大的最小的ri;
然后输出改边之后的有向图;
【题解】
如果整张图是一个环的话;
这个环上的每个点的答案就是确定的;
即为这个环的大小;
则考虑把原图缩点;
缩点之后;
每个环都能成为一个点;
则最后的答案就是强连通分量中所含节点个数最多的那个强连通分量的大小;
因为最后的图,经过缩点之后,肯定是一个有向无环图;
那么肯定有一个点它是没有出度的了;
则,让那个点所包含的节点个数最多;
这样,就能保证那个环上的点的r[i]最少,且为那个环的大小(环也即那个缩点之后没有出度的点);
然后写个dfs求出符合要求的图就好;
只要让每个联通分量内部成为环,然后外部,都朝向那个答案节点直接或间接连边就好;
建边的时候有技巧吧.
【Number Of WA】
2
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 4e5+100;
int n,m;
vector <pii> G[N];
pii a[N];
int dfn[N],low[N],z[N],tot=0,top = 0,root,ma;
void dfs1(int x,int fa)
{
dfn[x] = low[x] = ++tot;
z[++top] = x;
for (pii temp:G[x])
{
int y = temp.fi;
if (y==fa) continue;
if (!dfn[y])
dfs1(y,x);
low[x] = min(low[x],low[y]);
}
if (low[x]==dfn[x])
{
int num = 0,v = 0;
while (v!=x)
{
v = z[top];
num++,top--;
}
if (num>ma)
{
ma = num;
root = x;
}
}
}
void dfs2(int x,int fa)
{
dfn[x]=0;
for (pii temp:G[x])
{
int y = temp.fi,id = temp.se;
if (y==fa) continue;
if (dfn[y])
{
a[id]=mp(y,x);
dfs2(y,x);
}
else
a[id]=mp(x,y);
}
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
//init??????
cin >> n >> m;
rep1(i,1,m)
{
int x,y;
cin >> x >> y;
G[x].pb(mp(y,i)),G[y].pb(mp(x,i));
}
dfs1(1,0);
dfs2(root,0);
cout << ma<<endl;
rep1(i,1,m)
cout << a[i].fi <<' '<<a[i].se<<endl;
return 0;
}
最新文章
- [原]Paste.deploy 与 WSGI, keystone 小记
- os模块汇总
- C#控制台项目更改运行文件
- cf 700 A As Fast As Possible
- Tornado sqlalchemy
- 2013年7月底至8月初51Aspx源码发布详情
- USACO Section 3.3 游戏 A Game
- c/c++常用代码--udp多播
- [swustoj 785] Divide Tree
- Docker 监控实战
- 依賴注入入門——Unity(一)
- MVC-Model数据注解(三)-Remote验证的一个注意事项
- MXNet在64位Win7下的编译安装
- SpringBoot优化内嵌的Tomcat
- Ubuntu中MongoDB安装
- 为wampserver 添加新版本php支持
- java ———基础总结
- Python之使用转义序列 \n 和 \t 跟 expandtabs 函数输出表格
- 【设计经验】3、ISE中烧录QSPI Flash以及配置mcs文件的加载速度与传输位宽
- windows文件服务器的磁盘空间挂载在linux目录下使用