【训练】算法竞赛进阶指南-6图论

本处难度分档以个人实力为参照系
难度1:半小时内想出,半小时内ac
难度2:半小时想不出,看题解,服气
难度3:半小时想不出,看题解,ac后依然觉得难度很大

另外,由于追进度,对于coding部分比较有自信的题目,不再具体实现

0x60 图论

部分题目

1 poj3662 Telephone Lines

8.29 难度2

请先思考后再展开

找出一条从1到n的路径,上面第k+1大的那条边,权值最小
好弱啊第一题就不会做,天天看题解……

最小化除了前面k个以外的最大值,二分答案
把所有长度在mid以内的边看做0,否则1
跑一次最短路,如果花费在k以内,意味着可行
代码略

2 noip2009 最优贸易

8.29 难度2

请先思考后再展开

3 Usaco2011 Jan Gold 道路和航线

8.29 难度2

请先思考后再展开

这道题挺有意思的,本来以为是裸题想跳的,看到lyd说spfa会tle,就不想以身试法了
(网上说加上slf就好了……不过本着锻炼思维的理念,学习一下正解)
因为题目保证航线没有环,本来以为这仅仅是保证没有负环,
没想到这还是一个突破口(还有就是道路都是双向的这个性质)

如果只加入双向边,那么就会形成多个联通块
如果缩点后再加入单向航线,图会形成一个有向无环图,是可以通过拓扑得到最短路的
不过具体而言,不能真的缩点,因为需要具体得出每个点的最短路
大致上就是沿着负权边找到各个联通块,以拓扑为框架跳来跳去

具体的话有个细节:
就是有可能st所在的联通块,入度不为0
或者可能出了st联通块外,还有其他入度不为0的联通块
所以还是要按照平常拓扑那样,把所有入度为0的加入栈
不过为了防止,单源最短路被扰乱,应该先把st联通块的dis置0,这样无论如何也没法更新掉了
然后其他联通块的inf也应该设置大一点,这样即使被更新,也是一个很大的值
然后输出no path的时候,不能只是和inf比较,因为可能曾经被更新,
要看它是否明显超过理论正常最大距离( $T \times 10000=250000000$ ),设为0x3f3f3f3f就够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=31000,MAX_M=160000;
const ll INF=(1ll<<60);
int n;
struct Nod
{
int hou;
ll dis;
int uni;
Nod()
{
uni=hou=0;
dis=INF;
}
}p[MAX_N];
struct Edge
{
int y,c,g;
}e[MAX_M];
int ln=0;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,c,p[x].hou};
p[x].hou=ln;
}
int deg[MAX_N];
vector<int> vt[MAX_N];
void dfs(int x,int now)
{
p[x].uni=now;vt[now].push_back(x);
for(int k=p[x].hou;k>0;k=e[k].g) if(p[e[k].y].uni==0) dfs(e[k].y,now);
}
struct Que
{
ll d;
int x;
friend bool operator < (Que a,Que b) {return a.d>b.d;}
};
int sta[MAX_N],top=0;
priority_queue<Que> q;
void solve(int st)
{
for(int i=0;i<vt[p[st].uni].size();i++)
p[vt[p[st].uni][i]].dis=0;//确保不会被,st无法到达的块更新
for(int i=1;i<=n;i++) if(vt[i].size()>0 and deg[i]==0) sta[++top]=i;
while(top>0)//topsort
{
int t=sta[top--];
for(int i=0;i<vt[t].size();i++)
{
int x=vt[t][i];
if(t==p[st].uni and x!=st) p[x].dis=INF;//debug 漏了
q.push((Que){p[x].dis,x});
}
while(!q.empty())//dijkstra
{
Que now=q.top();q.pop();
int x=now.x;if(now.d!=p[x].dis) continue;//delete
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dis>p[x].dis+e[k].c)
{
p[y].dis=p[x].dis+e[k].c;
if(p[y].uni==p[x].uni) q.push((Que){p[y].dis,y});
}
if(p[y].uni!=p[x].uni)
{
deg[p[y].uni]--;
if(deg[p[y].uni]==0) sta[++top]=p[y].uni;
}
}
}
}
}
void main()
{
int ma,mb,st;scanf("%d%d%d%d",&n,&ma,&mb,&st);
while(ma--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
}
for(int i=1;i<=n;i++) if(p[i].uni==0) dfs(i,i);
while(mb--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);if(p[x].uni!=p[y].uni) deg[p[y].uni]++;
}
solve(st);
for(int i=1;i<=n;i++)
if(p[i].dis>0x3f3f3f3f) puts("NO PATH");
else printf("%lld\n",p[i].dis);
}
};
int main()
{
mine::main();
}

4 poj1734 Sightseeing trip

8.29 难度2

请先思考后再展开

floyd找最小环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110;
const int INF=0x3f3f3f3f;
int ans[MAX_N],ln;
int fm[MAX_N][MAX_N];
int dis[MAX_N][MAX_N],a[MAX_N][MAX_N];
void getans(int x,int y)
{
if(fm[x][y]<0) {ans[++ln]=x;return;}
int k=fm[x][y];
getans(x,k);getans(k,y);
}
void main()
{
int n,m;scanf("%d%d",&n,&m);
memset(a,63,sizeof a);
memset(fm,0,sizeof fm);
for(int i=1;i<=n;i++) a[i][i]=0;
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
if(c<a[x][y]) a[x][y]=a[y][x]=c,fm[x][y]=fm[y][x]=-1;
}
memcpy(dis,a,sizeof a);
int mi=INF;
for(int k=1;k<=n;k++)
{
for(int i=1;i<k;i++)
for(int j=i+1;j<k;j++)
{
ll tmp=(ll)dis[i][j]+a[j][k]+a[k][i];//debug 爆int
if(mi>tmp)
{
mi=tmp;
ln=0;getans(i,j);ans[++ln]=j;ans[++ln]=k;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) if(i!=j)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j],fm[i][j]=k;
}
if(mi==INF) puts("No solution.");//神tm漏了一个点……
else for(int i=1;i<=ln;i++) printf("%d ",ans[i]);
}
};
int main()
{
mine::main();
}

5 6201 走廊泼水节

8.29 难度2

请先思考后再展开

这道题设计得很好
个人很喜欢这种,对看似简单、经典的算法,推陈出新地挖掘细节、原理的题目
结果就不会做了……

这道题从边的角度思考会简单一些
想到边,以及最小生成树,会想到kruskal
把所有边排序,然后关键就是“完全图中的边,是否跨树”
对于这一点我只能出个数据把自己的乱搞做法卡掉,但不知道怎么去解决

其实这条边什么时候会跨树呢?
盗lyd好图:

是不是豁然开朗了?
模拟kruskal的过程,连接两个树之间的边,只会在这一次跨树
此时,他们的取值都应为z+1,个数则是 $Sx \times Sy-1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=6100;
const int INF=0x3f3f3f3f;
struct Edge
{
int x,y,c;
}e[MAX_N];
bool cmp(Edge a,Edge b) {return a.c<b.c;}
int fa[MAX_N],siz[MAX_N];
int findfa(int x) {return fa[x]=(x==fa[x]?x:findfa(fa[x]));}
void main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;
for(int i=1;i<=n-1;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
sort(e+1,e+n-1+1,cmp);
ll ans=0;
for(int i=1;i<=n-1;i++)
{
int x=e[i].x,y=e[i].y;
int fx=findfa(x),fy=findfa(y);
ans+=ll(e[i].c+1)*( (ll)siz[fx]*siz[fy]-1 );
if(fx!=fy) fa[fx]=fy,siz[fy]+=siz[fx];//merg
}
printf("%lld\n",ans);
}
}
};
int main()
{
mine::main();
}

6 poj1639 Picnic Planning

8.30 难度2

请先思考后再展开

就是限制了根节点度数的最小生成树
先去除1节点,跑出每个节点的最小生成树,然后找最小的一条边连接上去
然后有可能可以对某个点x,去掉某条1到x的一条边,并连接x和1

7 poj2728 Desert King

8.30 难度1

请先思考后再展开

01分数规划+最小生成树
不过不知道为什么跑得很慢
log的大小,无论如何都是在100以内的,那么正常来说这道题就一亿,时限3s
个人觉得它非要卡二分我也没办法,Dinkelbach大概只是恰好快而已(毕竟那东西的复杂度很玄学)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=1100;
const int INF=0x3f3f3f3f;
double myabs(double x) {return x>0?x:-x;}
const double eps=1e-8;
struct Nod
{
int x,y;
int h;
}p[MAX_N];
double dis(double x1,double y1,double x2,double y2) {return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );}
int n;
double L;
double d[MAX_N],a[MAX_N][MAX_N],cst[MAX_N][MAX_N],ln[MAX_N][MAX_N];
bool v[MAX_N];
bool check()//prim<=0
{
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=cst[i][j]-L*ln[i][j];
d[0]=INF;d[1]=0;for(int i=2;i<=n;i++) d[i]=a[1][i];
memset(v,0,sizeof v);v[1]=1;
double sum=0;
for(int cnt=1;cnt<=n-1;cnt++)
{
int t=0;for(int i=1;i<=n;i++) if(!v[i] and d[i]<d[t]) t=i;
sum+=d[t];v[t]=1;
for(int i=1;i<=n;i++) if(!v[i] and a[t][i]<d[i]) d[i]=a[t][i];
}
return sum<=eps;
}
/*
int m;
struct Edge
{
int x,y;
double cst,ln;
}e[MAX_N*MAX_N];
bool cmp(Edge a,Edge b) {return a.cst-L*a.ln<b.cst-L*b.ln;}
int fa[MAX_N];
int findfa(int x) {return fa[x]=(x==fa[x]?x:findfa(fa[x]));}
bool check()//kruskal<=0 沙茶了,完全图用kruskal……
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i;//debug
double sum=0;
for(int i=1;i<=m;i++)
{
int x=e[i].x,y=e[i].y;
int fx=findfa(x),fy=findfa(y);
if(fx!=fy)
{
sum+=e[i].cst-L*e[i].ln;
fa[fx]=fy;
}
}
return sum<=0;
}*/
void main()
{
while(1)
{
scanf("%d",&n);
if(n==0) break;
for(int i=1;i<=n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].h);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cst[i][j]=myabs(p[i].h-p[j].h),ln[i][j]=dis(p[i].x,p[i].y,p[j].x,p[j].y);
double l=0,r=INF,ans=-1;
while(l<=r+eps)
{
L=(l+r)/2;
if(check()) ans=L,r=L-eps;
else l=L+eps;
}
printf("%.3lf\n",ans);
}
}
};
int main()
{
mine::main();
}

8 APIO2010 巡逻

8.30 难度2

请先思考后再展开

这道题的k=1、2,先从k=0入手
不难发现,每条边一定要经过两次(因为是树,一定会递归一次回溯一次),所以就是$2(n-1)$
对于k=1,加入一条新的边以后,一定出现了环,就不一定是两次了
同时,在这个环上,其他边都从经过两次变成了经过一次(例如题目中的a)
不难发现,此时答案为$2(n-1)-(直径长度-1)$

对于k=2的情况,稍微复杂了一些
如果产生的新的环,没有和原本的环重叠,那么同样是不用经过一次(例如题目中的b)
但是,如果重叠了(例如题目中的c),那么由于“新的边必须经过一次”这个限制,公共部分又变成了要经过两次

总上所述,第一次找直径L1,把边权变为-1
第二次找到直径L2,答案即$2(n-1)-(L1-1)-(L2-1)$

有木有觉得apio的图片非常良心

9 CH#56C 异象石

8.30 难度2

请先思考后再展开

先从每个节点上都有石头的情况开始考虑
如果从边的角度,那就是边总长
但因为这道题,主要从点的情况考虑,所以转化为,按照dfs搜索顺序,经过的相邻两点间距离/2
而对于不满的情况也是类似,把存在的所有点,按照dfs序收尾相接,相邻间距离和即为答案
那么具体实现的时候,可以搞一个set,用upper_bound等找相邻并动态维护当前总和即可

10 BJWC2010 严格次小生成树

8.30 难度2

请先思考后再展开

按照惯例,对于这种在树上有非树边的问题,可以考虑一下,由非树边产生的环
例如本题,对于这个环,我们断掉任何一个,整个图依然是树(本来就是挂起来的无向无环图)
所以说,对于每条边,其贡献就是,把它替换掉原本树上路径中最大那一条产生的差
然后因为求的是严格次小,所以有种特殊情况,就是最大那个和当前边相同长

引理:
在最小生成树原本的路径中,一定不会有比当前非树边大的边

证明:
否则应该被当前非树边替换掉(替换掉一定不会有其他副作用之类,还是那句话,树本来就是挂起来的无向无环图)

那么也就是我们还需要且只需要再考虑次大值
具体实现的话,用一个倍增st表维护一下就好了(以倍增lca为框架)

11 IOI2008 Island

8.30 难度1

请先思考后再展开

题意为,给出一个基环树森林,每个节点只能去一次,起点任意
跨基环树的时候,不能回到曾经去过的基环树
求最大化的【经过的基环树边的总和】
显然答案就是每个基环树内直径之和
然后基环树直径这种东西,写个dfs找环,dfs向下找最大深度,然后套个单调队列就好了

12 6401 创世纪

8.30 难度2

请先思考后再展开

在lxj的提醒下才想到正解……
其实一点都不难

图显然是一个内向树森林,要求选自己,则至少一个孩子不被选
考虑dp,$f(x,0/1)$表示当前子树满足条件时,x选择0/1的最大选择节点数
先搞定树上的部分,如果枚举固定一个孩子不选,然后其他乱搞,但给个菊花图就会炸
不难想到取补,把任意情况减去所有孩子都选了的情况(套路之记录次小值)

对于环上的怎么搞呢?
看一眼这里就知道了

13 POI2008 BLO-Blockade

8.31 难度2

请先思考后再展开

教程
然后还是不会做……

在搜索树上考虑
对于每个节点,假如它不是割点,那么只有它和其他人是联通块,贡献为$2(n-1)$
而如果是割点,我们需要知道产生了多少个联通块,以及他们的大小

但怎么找?
$low_y \leq dfn_x$
这等价于割点的判定条件
主要考虑是可以相等,因为每次我们会断掉所有的边

联通块有三种:

  1. x自己,大小1
  2. 共有t个满足上面的条件,大小为在搜索树上的子树大小
  3. 剩下的所有点(假如大小不为0,则一定存在)

第三点非常容易想漏,所以说建议多构造几组数据,当然对拍也是可以如果求稳的话

时间复杂度$O(n+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int MAX_N=110000,MAX_M=510000;
const int INF=0x3f3f3f3f;
int mymax(int x,int y) {return x>y?x:y;}
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
int hou;
int siz;
int dfn,low;
ll ans;
Nod() {hou=dfn=siz=0;ans=0;}
}p[MAX_N];
struct Edge
{
int y,g;
}e[MAX_M*2];
int ln=0;
void ins(int x,int y) {e[++ln]=(Edge){y,p[x].hou};p[x].hou=ln;}
int oth(int t) {return (t&1)?t+1:t-1;}
int id=0;
int n;
void tarjan(int x,int from)
{
p[x].siz=1;
p[x].dfn=p[x].low=++id;
int sum=0,cnt=0;bool cut=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dfn==0)
{
tarjan(y,k);
p[x].siz+=p[y].siz;
p[x].low=mymin(p[x].low,p[y].low);
if(p[y].low>=p[x].dfn)
{
cnt++;
p[x].ans+=(ll)p[y].siz*(n-p[y].siz);
sum+=p[y].siz;
if(x!=1 or cnt>1) cut=1;
}
}
else if(k!=oth(from)) p[x].low=mymin(p[x].low,p[y].dfn);
}
if(cut) p[x].ans+=ll(n-sum-1)*(sum+1)+(n-1);
else p[x].ans=2*(n-1);//注意要直接赋值
}
void main()
{
int m;scanf("%d%d",&n,&m);
while(m--) {int x,y;scanf("%d%d",&x,&y);ins(x,y);ins(y,x);}//无重边
tarjan(1,-1);
for(int i=1;i<=n;i++) printf("%lld\n",p[i].ans);
}
};
int main()
{
mine::main();
}

14 poj3694 Network

8.31 难度1

请先思考后再展开

教程
考虑合并每个e-DCC,形成一棵树
然后倍增预处理一下lca

然后对于操作,其实就是合并x到y树上路径上的所有点,这个可以考虑用并查集维护
由于单个的小合并操作,只会发生n次,即使并查集log,也只有nlogn
而这个复杂度是超脱于询问这个循环之外的总复杂度

其实细节挺多的,大致流程:

  1. tarjan找到e-DCC,确定代表元素,初始化其并查集(最后别漏了根节点)
  2. 建立新的边目录,预处理倍增lca
  3. 回答询问的时候,一个个向上跳,维护割边数量cnt
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    //Zory-2018
    #include<cmath>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<map>
    #include<set>
    #include<queue>
    #include<deque>
    #include<bitset>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    namespace mine
    {
    typedef long long ll;
    #define double long double
    const int MAX_N=110000,MAX_M=410000;
    const int INF=0x3f3f3f3f;
    int mymax(int x,int y) {return x>y?x:y;}
    int mymin(int x,int y) {return x<y?x:y;}
    struct Nod
    {
    int hou;
    int dfn,low;
    int fa;//块父亲
    }p[MAX_N];
    struct Edge
    {
    int x,y,g;
    }e[MAX_M*2];
    int ln;
    void ins(int x,int y)
    {
    ln++;
    e[ln].x=x;e[ln].y=y;
    e[ln].g=p[x].hou;
    p[x].hou=ln;
    }
    int oth(int t) {return (t&1)?(t+1):(t-1);}
    int id[MAX_N];//并查集维护,所在的块
    int findfa(int x) {return id[x]=(x==id[x]?x:findfa(id[x]));}
    void dfs(int x,int fa,int now)
    {
    id[x]=now;
    for(int k=p[x].hou;k>0;k=e[k].g) if(e[k].y!=fa and id[e[k].y]==0) dfs(e[k].y,x,now);
    }
    int ct,cnt;
    void tarjan(int x,int from)
    {
    p[x].dfn=p[x].low=++ct;
    for(int k=p[x].hou;k>0;k=e[k].g)
    {
    int y=e[k].y;
    if(p[y].dfn==0)
    {
    tarjan(y,k);
    p[x].low=mymin(p[x].low,p[y].low);
    if(p[y].low>p[x].dfn)//割边
    {
    cnt++;//割边数
    p[y].fa=x;
    dfs(y,x,y);
    }
    }
    else if(k!=oth(from)) p[x].low=mymin(p[x].low,p[y].dfn);
    }
    }
    int hou[MAX_N],dep[MAX_N];
    Edge e2[MAX_M*2];
    int ln2;
    void ins2(int x,int y)
    {
    ln2++;
    e2[ln2].y=y;e2[ln2].g=hou[x];
    hou[x]=ln2;
    }
    int f[MAX_N][20];
    void pre(int x,int fa)
    {
    dep[x]=dep[fa]+1;
    f[x][0]=fa;for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int k=hou[x];k>0;k=e2[k].g)
    {
    int y=e2[k].y;if(y==fa) continue;
    pre(y,x);
    }
    }
    int n,m;
    void make_graph()
    {
    ln=0;for(int i=1;i<=n;i++) p[i].hou=p[i].dfn=0;
    for(int i=1;i<=m;i++)
    {
    int x,y;scanf("%d%d",&x,&y);
    ins(x,y);ins(y,x);//无自环
    }
    cnt=0;ct=0;memset(id,0,sizeof id);
    tarjan(1,-1);dfs(1,0,1);
    ln2=0;memset(hou,0,sizeof hou);
    for(int i=1;i<=2*m;i+=2)
    {
    int fx=findfa(e[i].x),fy=findfa(e[i].y);
    if(fx!=fy) ins2(fx,fy),ins2(fy,fx);
    }
    pre(1,0);
    }
    int bin[20];
    int getlca(int x,int y)
    {
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=19;i>=0;i--) if(dep[x]-dep[y]>=bin[i]) x=f[x][i];
    if(x==y) return x;
    for(int i=19;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
    }
    int solve()
    {
    int x,y;scanf("%d%d",&x,&y);
    int fx=findfa(x),fy=findfa(y),lca=findfa(getlca(fx,fy));//debug getlca(x,y)
    while(fx!=lca) cnt--,id[fx]=lca,fx=findfa(p[fx].fa);
    while(fy!=lca) cnt--,id[fy]=lca,fy=findfa(p[fy].fa);
    //因为每次findfa找最上面的代表元素,所以p[fx].fa一定是另一个节点
    return cnt;
    }
    void main()
    {
    bin[0]=1;for(int i=1;i<20;i++) bin[i]=bin[i-1]<<1;
    int cas=0;
    while(1)
    {
    scanf("%d%d",&n,&m);
    if(n==0) break;
    printf("Case %d:\n",++cas);
    make_graph();
    int q;scanf("%d",&q);
    while(q--) printf("%d\n",solve());
    }
    }
    };
    int main()
    {
    mine::main();
    }

15 poj2942 Knights of the Round Table

9.1 难度2

请先思考后再展开

题意:找出有多少个骑士,无法出席任何会议
会议的要求是有奇数个人,成环形后相邻的人没有憎恨关系

因为是环形,考虑连成一个环,不难想到建立一个补图,用【无憎恨关系】来建边
那么就转化成,有多少个点,不在任何奇环(奇数个点的简单环)中

然后判断奇环可以染色,但怎么标记呢?暴力搞我自己都能出个数据卡成nm
百思不得其姐,又去膜题解
题解给出的又是两个结论……还好这一次,这两个结论的证明都很简单

结论1:奇环不会垮v-DCC存在
证明:显然两个v-DCC能合并成一个v-DCC,与v-DCC的“极大”矛盾

结论2:如果某个v-DCC中有奇环,则整个v-DCC的每个节点,至少被一个奇环所包含
假设有奇环外节点x,总是能和奇环上任意两个节点vi和vj形成奇环,
因为无论【x到vi+x到vj】的奇偶性如何,奇环上两个点间距离总是能取奇数或者偶数……
因为奇=奇+偶,亘古不变……

怎么说呢?这两个结论都不是太好猜,但偏偏缺一不可

16 poj1236 Network of Schools

9.1 难度2

请先思考后再展开

开始想法:
设强连通分量缩点后,a=【入度=0】,b=【出度=0】
那么第一问求a,第二问求b

其实已经和正解接近了,但还是错误的
第二问求的其实是max(a,b)
重新思考,
对于入度为0的scc,如果起点不在这里就凉了,要消除掉
对于出度为0的scc,如果起点在这里就凉了,要消除掉
因为一次可以同时消除两种各一个,得证

17 poj2226 Muddy Fields

9.7 难度2

请先思考后再展开

不会做的经典模型
将连续的泥地分为行泥泞块和列泥泞块,形成了二分图
那么,对于每个小泥地,至少要被其中一种覆盖
那么把每个小泥地作为边,恰好连接两个元
求最小覆盖即可

18 6902 Vani和Cl2捉迷藏

9.9 难度2

请先思考后再展开

神仙结论题,结论不好猜,证明不好想,但出得挺好
因为不能有路径相连,可以联想到传递闭包(居然没有想到),转移为边的相连(构造新图,边就是用闭包得出来的结果)
那么现在类似于要找最大独立集

结论:总能在【最小可重复点覆盖路径】的每条路径中,找出一个点
证明:
首先,【隐藏点】显然小于等于【路径数量】
那么我们只要说我们能构造出一种方法来,就相当于证明了结论(这也是一种有趣的证明方法)

先取出每个路径的终点,作为集合A,将A走一步能到达的节点作为next(A)
按照题意,$A \cap next(A)=\varnothing$ ,所以我们要有所调整
取出这种元素,然后在其所属的【最小可重复点覆盖路径】上,往起点方向跳,
一定能找到一个元素不属于next(A),否则意味着整条路径都是可以被别人覆盖掉的,违反了我们先前最小的定义
找到后,取代原先的元素,如此重复下去,最后总是能满足条件的
综上所述,存在一种方案,满足条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int MAX_N=210;
int n,m;
int match1[MAX_N],match2[MAX_N];
int ask[MAX_N],ti;//时间戳
bool mp[MAX_N][MAX_N];
bool fd(int x)
{
for(int y=1;y<=n;y++)
{
if(!mp[x][y] or ask[y]==ti) continue;
ask[y]=ti;
if(match2[y]==0 or fd(match2[y]))
{
match1[x]=y;
match2[y]=x;
return 1;
}
}
return 0;
}
bool A[MAX_N],Anx[MAX_N];
int up(int x) {return match2[x];}
void main()
{
scanf("%d%d",&n,&m);
while(m--)
{
int x,y;scanf("%d%d",&x,&y);
mp[x][y]=1;
}
//传递闭包
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j]|=mp[i][k]&mp[k][j];
//二分图匹配
int ans=0;for(ti=1;ti<=n;ti++) ans+=fd(ti);
printf("%d\n",n-ans);
for(int i=1;i<=n;i++) if(match1[i]==0) A[i]=1;
bool modif=1;
while(modif)
{
modif=0;
memset(Anx,0,sizeof Anx);
for(int i=1;i<=n;i++) if(A[i])
for(int j=1;j<=n;j++) if(mp[i][j]) Anx[j]=1;
for(int i=1;i<=n;i++) if(A[i] and Anx[i])
{
modif=1;
int t=up(i);while(Anx[t]) t=up(t);
A[i]=0;A[t]=1;
break;
}
}
for(int i=1;i<=n;i++) if(A[i]) printf("%d ",i);
}
};
int main()
{
mine::main();
}

19 CH#17 舞动的夜晚

9.10 难度2

请先思考后再展开

详见oi之路的二分图一章

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=11000,MAX_M=110000;
int mymin(int x,int y) {return x<y?x:y;}
struct Nod
{
int hou;
bool v;
Nod() {hou=0;v=0;}
}p[MAX_N*2];
struct Edge
{
int y,g,c;
}e[(MAX_N*2+MAX_M)*2];
int oth(int x) {return x&1?x+1:x-1;}
int ln=0;
void ins(int x,int y,int c)
{
e[++ln]=(Edge){y,p[x].hou,c};p[x].hou=ln;
e[++ln]=(Edge){x,p[y].hou,0};p[y].hou=ln;
}
int st,ed;
int h[MAX_N*2];
queue<int> q;
bool bfs()
{
memset(h,0,sizeof h);
q.push(st);h[st]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==0 and e[k].c>0)
{
h[y]=h[x]+1;
q.push(y);
}
}
}
return h[ed]>0;
}
int dfs(int x,int flow)
{
if(x==ed) return flow;
int out=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y,fine=mymin(flow-out,e[k].c);
if(h[y]==h[x]+1 and fine>0)//注意e[k].c,可能改变了
{
int t=dfs(y,fine);
out+=t;e[k].c-=t;e[oth(k)].c+=t;
}
}
if(out==0) h[x]=0;//剪枝
return out;
}
int dfn[MAX_N*2],low[MAX_N*2],id=0;
int sta[MAX_N*2],top=0;
bool insta[MAX_N*2];
int belg[MAX_N*2],cnt=0;
void tarjan(int x)
{
dfn[x]=low[x]=++id;
sta[++top]=x;insta[x]=1;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(e[k].c==0) continue;
if(dfn[y]==0) tarjan(y),low[x]=mymin(low[x],low[y]);
else if(insta[y]) low[x]=mymin(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
++cnt;
int now;
do
{
now=sta[top--];
belg[now]=cnt;
insta[now]=0;
}while(now!=x);
}
}
int xx[MAX_M],yy[MAX_M];
void main()
{
int n,m,ct;scanf("%d%d%d",&n,&m,&ct);
st=0,ed=n+m+1;
for(int i=1;i<=n;i++) ins(st,i,1);
for(int i=1;i<=m;i++) ins(n+i,ed,1);
for(int i=1;i<=ct;i++)
{
scanf("%d%d",&xx[i],&yy[i]);
ins(xx[i],n+yy[i],1);
}
while(bfs()) dfs(st,0x3f3f3f3f);
for(int i=st;i<=ed;i++) if(dfn[i]==0) tarjan(i);
int tot=0;
for(int i=1;i<=ct;i++)
tot+=(e[2*(n+m+i-1)+1].c==0 or belg[xx[i]]==belg[n+yy[i]]);
printf("%d\n",ct-tot);
for(int i=1;i<=ct;i++)
if(e[2*(n+m+i-1)+1].c==0 or belg[xx[i]]==belg[n+yy[i]]) ;
else printf("%d ",i);
}
};
int main()
{
mine::main();
}

20 Poj3422 Kaka’s Matrix Travels

9.10 难度1

请先思考后再展开

考虑用流量表示路径的移动
然后因为每个格子只能取一次,拆一下点
$st=>(1,1,0),flow=k,cost=0$
$(i,j,0)=>(i,j,1),flow=1,cost=num(i,j)$
$(i,j,0)=>(i,j,1),flow=\infty,cost=0$
$(i,j,1)=>(i+tx[t],j+ty[t],0),flow=\infty,cost=0$
$(n,n,1)=>ed,flow=\infty,cost=0$
跑最大费用最大流即可

0x6B 图论练习

部分题目

21 6B02 升降梯上

9.11 难度1

请先思考后再展开

把每个点拆成m个操作后的状态,最短路即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=21000;
const int INF=0x3f3f3f3f;
int myabs(int x) {return x>0?x:-x;}
struct Nod
{
int hou;
int dis;
Nod() {hou=0;dis=INF;}
}p[MAX_N];
struct Edge
{
int y,c,g;
}e[MAX_N*30];
int ln=0;void ins(int x,int y,int c) {e[++ln]=(Edge){y,c,p[x].hou};p[x].hou=ln;}
int st,ed;
struct Data
{
int dis,id;
friend bool operator > (Data a,Data b) {return a.dis>b.dis;}
};
priority_queue< Data,vector<Data>,greater<Data> > q;
void dijkstra()
{
p[st].dis=0;q.push((Data){p[st].dis,st});
while(!q.empty())
{
Data t=q.top();q.pop();
int x=t.id;if(p[x].dis<t.dis) continue;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].dis>p[x].dis+e[k].c)
{
p[y].dis=p[x].dis+e[k].c;
q.push((Data){p[y].dis,y});
}
}
}
}
int n,m;
int c[30];
int calc(int x,int y) {return (x-1)*m+y;}
void main()
{
scanf("%d%d",&n,&m);
st=0;ed=n*m+1;
for(int j=1;j<=m;j++)
{
scanf("%d",&c[j]);
if(c[j]==0) ins(st,calc(1,j),0);
}
for(int i=1;i<n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=m;k++)
if(1<=i+c[k] and i+c[k]<=n)
ins(calc(i,j),calc(i+c[k],k),myabs(j-k)+2*myabs(c[k]));
for(int j=1;j<=m;j++) ins(calc(n,j),ed,0);
dijkstra();
printf("%d",p[ed].dis==INF?-1:p[ed].dis);
}
};
int main()
{
mine::main();
}

22 NOI2007 社交网络

9.11 难度2

请先思考后再展开

原来最短路路径数是可以用floyd统计的
然后记住一定要去除编号相同的情况(以前总是偷懒)
还有就是,一开始总是想不通怎么处理一条链的情况,为什么不会重复统计呢?
但其实,由于其dp性质,一条路径只会在k为最大编号时才被统计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=110;
typedef long long ll;
int mp[MAX_N][MAX_N];
ll cnt[MAX_N][MAX_N];
void main()
{
memset(mp,0x3f,sizeof mp);
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) mp[i][i]=0,cnt[i][i]=1;
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
mp[x][y]=mp[y][x]=c;
cnt[x][y]=cnt[y][x]=1;
}
//因为floyd的dp性质,左右两边只经过小于当前编号的节点,所以不会计算重复
for(int k=1;k<=n;k++)
for(int x=1;x<=n;x++) if(x!=k)//避免重复情况
for(int y=1;y<=n;y++) if(y!=k and y!=x)
{
if(mp[x][y]>mp[x][k]+mp[k][y])
{
mp[x][y]=mp[x][k]+mp[k][y];
cnt[x][y]=cnt[x][k]*cnt[k][y];
}
else if(mp[x][y]==mp[x][k]+mp[k][y])
cnt[x][y]+=cnt[x][k]*cnt[k][y];
}
for(int x=1;x<=n;x++)
{
double ans=0;
for(int st=1;st<=n;st++) if(st!=x)
for(int ed=1;ed<=n;ed++) if(ed!=x)
if(mp[st][x]+mp[x][ed]==mp[st][ed])
ans+=(double)cnt[st][x]*cnt[x][ed]/cnt[st][ed];
printf("%.3lf\n",ans);
}
}
};
int main()
{
mine::main();
}

23 NOI2003 逃学的小孩

9.12 难度2

请先思考后再展开

说来惭愧,其实不难
最小化答案:min(c->a,c->b)+a->b
然后因为所有直径都是等效的,可以证明a->b的增加,左边不会降低
所以说,直接取a->b为直径,然后扫描一下就好了

24 AHOI2008 紧急集合

9.12 难度2

请先思考后再展开

又感到很惭愧了……
想了些数据,发现一定是跑到其中一个lca
然后又yy几个情况,发现都是应该找深度最小那两个,然后到他们的lca,就不用枚举三次了
然后就秒wa了
然后就被rose秒出hack数据了,就是深度大那个点在它们到lca之间的路径上……
所以最后还是枚举,发现有点慢,最大0.93s……
所以正解应该是用离线lca算法,不过太复杂就不改了,大概yy了一下算法权当复习

下面就只给出朴素代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=510000;
struct Nod
{
int hou;
int dep;
Nod() {hou=dep=0;}
}p[MAX_N];
struct Edge
{
int y,g;
}e[MAX_N*2];
int ln=0;void ins(int x,int y) {e[++ln]=(Edge){y,p[x].hou};p[x].hou=ln;}
int bin[21];
int f[MAX_N][21];
void pre(int x,int fa)
{
p[x].dep=p[fa].dep+1;
f[x][0]=fa;for(int i=1;i<20;i++) f[x][i]=f[f[x][i-1]][i-1];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
pre(y,x);
}
}
int LCA(int x,int y)
{
if(p[x].dep<p[y].dep) swap(x,y);
for(int i=20;i>=0;i--) if(p[x].dep-p[y].dep>=bin[i]) x=f[x][i];
if(x==y) return x;
for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int dis(int x,int y) {return p[x].dep+p[y].dep-2*p[LCA(x,y)].dep;}
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
int n,q;scanf("%d%d",&n,&q);
for(int i=1;i<=n-1;i++)
{
int a,b;scanf("%d%d",&a,&b);
ins(a,b);ins(b,a);
}
pre(1,0);
while(q--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int lca1=LCA(a,b),lca2=LCA(b,c),lca3=LCA(a,c);
int c1=(p[a].dep-p[lca1].dep)+(p[b].dep-p[lca1].dep)+dis(lca1,c);
int c2=(p[b].dep-p[lca2].dep)+(p[c].dep-p[lca2].dep)+dis(lca2,a);
int c3=(p[a].dep-p[lca3].dep)+(p[c].dep-p[lca3].dep)+dis(lca3,b);
if(c1<=c2 and c1<=c3) printf("%d %d\n",lca1,c1);
else if(c2<=c1 and c2<=c3) printf("%d %d\n",lca2,c2);
else printf("%d %d\n",lca3,c3);
}
}
};
int main()
{
mine::main();
}

25 poj1275 Cashier Employment

9.13 难度2

请先思考后再展开

本来想着如果在费用流统计答案的时候不把费用乘以流量,就能让边权只表示使用这条边的费用
那么就可以构图,从st到每个人,流量8费用1,然后时间连向ed,流量就是需求量
然后发现这样的修改没有用,因为我可能流量在下一条增广路采用,然后费用就被多次统计了……
看了眼tag居然是差分约束……

不难想到可以前缀和一下,构造不等式组
不过不知道怎么处理环形的情况,好像涉及了三个元
$s[i] \geq s[i-1]$
$当i leq 7,s[i]+tot-s[i+15] \geq c[i]$
$otherwise,s[i]-s[i-8] \geq c[i]$

膜lxj后发现,显然的单调性,二分即可

26 6B12 最优高铁环

9.13 难度2

请先思考后再展开

连01规划的sb题都不会做了
有点担忧……现在才相同专题都这样,感觉后面要更多地做综合题
对于有思考环节深度的题目,经常比别人走得浅
当别人在关心判正环太慢的时候,我还毫无思路
甚至别人以为我没去做例题……

总之这道题为了判断负环的速度,写的是栈spfa
如果在初始值为0的情况下,只要存在最长路的松弛,就是产生了正环
然后不知为何本机ac提交wa

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=1100;
typedef long long ll;
int hou[5*MAX_N];
struct Edge
{
int y,g,c;
}e[51000];
int ln=0;void ins(int x,int y,int c) {e[++ln]=(Edge){y,hou[x],c};hou[x]=ln;}
double dis[5*MAX_N];
bool v[5*MAX_N];
bool dfs(int x,double mid)
{
v[x]=1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dis[y]<dis[x]+e[k].c-mid)
{
if(v[y]) return 1;
dis[y]=dis[x]+e[k].c-mid;
if(dfs(y,mid)) return 1;
}
}
v[x]=0;
return 0;
}
bool check(double mid)
{
memset(v,0,sizeof v);
memset(dis,0,sizeof dis);
for(int i=1;i<=5000;i++) if(dfs(i,mid)) return 1;
return 0;
}
int sum;bool bk;
int getid()
{
char c=getchar();
char c2=getchar();int t=0;
while('0'<=c2 and c2<='9') t=t*10+c2-'0',c2=getchar();
bk=(c2=='-');
if(c=='S') {sum+=1000;return t;}
if(c=='G') {sum+=500;return 1000+t;}
if(c=='D') {sum+=300;return 2000+t;}
if(c=='T') {sum+=200;return 3000+t;}
sum+=150;return 4000+t;
}
void main()
{
int m;scanf("%d",&m);getchar();
for(int i=1;i<=m;i++)
{
sum=0;
int st=getid();
int ed=getid();
while(bk) ed=getid();
ins(st,ed,sum);
}
ll l=0,r=(ll)1000*20*50000*10,ans=-1;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check((double)mid/10)) ans=mid,l=mid+1;
else r=mid-1;
}
if(ans<0) puts("-1");
else printf("%d",(int)round( (double)ans/10 ));
}
};
int main()
{
mine::main();
}

27 HNOI2012 矿场搭建

9.14 难度2

请先思考后再展开

显然先求一下割点,求出每个块的组成
分析每个块,如果内部没有割点,那么需要两个出口,位置任意,但不重复
如果只有一个割点,那么堵掉就凉了,所以要添加出口,而且不能在割点处
如果有两个或以上,那么就无需担心,总能够出去
综上说述,乘法原理统计一下即可

然后我以为根节点那个特判会影响vdcc的判断,其实只是影响割点……没有好好思考
还有就是完全没考虑孤立点,还好这道题不需要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=110000;
typedef long long ll;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
int hou[MAX_N];
struct Edge
{
int y,g;
}e[MAX_N];
int oth(int x) {return x&1?x+1:x-1;}
int ln;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int cnt;vector<int> vdcc[MAX_N];
bool gd[MAX_N];
int id,dfn[MAX_N],low[MAX_N];
int sta[MAX_N],top;bool insta[MAX_N];
void tarjan(int x,int fm)
{
sta[++top]=x;insta[x]=1;
dfn[x]=low[x]=++id;
int son=0;//debug 这个不能影响vdcc的判定条件,只是和是否割点有关
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(k==oth(fm)) continue;
if(dfn[y]==0)
{
tarjan(y,k);low[x]=mymin(low[x],low[y]);
if(low[y]>=dfn[x] or (fm==0 and son>=2))//块
{
son++;vdcc[++cnt].clear();
if(fm!=0 or son>=2) gd[x]=1;
while(1)
{
int now=sta[top--];
vdcc[cnt].push_back(now);
if(now==y) break;
}
vdcc[cnt].push_back(x);
}
}
else if(insta[y]) low[x]=mymin(low[x],dfn[y]);
}
//debug 注意我忘记考虑孤立点的情况了
//但因为这道题没有自环,也确实不用考虑
}
void main()
{
int ct=0;
while(1)
{
int n;scanf("%d",&n);
if(n==0) break;
ln=0;memset(hou,0,sizeof hou);
int mx=0;
for(int i=1;i<=n;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
mx=mymax(mx,mymax(x,y));
}
id=top=cnt=0;
memset(insta,0,sizeof insta);
memset(gd,0,sizeof gd);
memset(dfn,0,sizeof dfn);
for(int i=1;i<=mx;i++) if(dfn[i]==0) tarjan(i,0);
ll tot=0,ans=1;
for(int i=1;i<=cnt;i++)
{
int siz=vdcc[i].size();
int dg=0;for(int j=0;j<siz;j++) if(gd[vdcc[i][j]]) dg++;
if(dg==0) tot+=2,ans*=(ll)siz*(siz-1)/2;
if(dg==1) tot++,ans*=siz-1;
}
printf("Case %d: %lld %lld\n",++ct,tot,ans);
}
}
};
int main()
{
mine::main();
}

28 bzoj3033 太鼓达人

9.15 难度2

请先思考后再展开

非常好的一道题,如果lxj不说是欧拉图我肯定不会做……
先考虑长度,显然不会超过 $2^k$ ,否则一定会出现重复
那么如果我们能构造出一种方案,保证长度为 $2^k$ ,那么答案就是 $2^k$

假设该结论成立,那么我们需要覆盖 0~ $2^k-1$ 的每个值
有一个不那么好像的方法,但因为自己受到提示,不难想到把每个值作为边
然后为了确保出现的独一无二,分割为前面k-1个和后面k-1个,转移的边为了字典序优先选最小的
那么因为出度为2,入度为2,一定是一个欧拉图,那么一定能得出 $2^k$ 的长度0

如果讲得不清楚,这位女选手的图片不错

29 中山市选 杀人游戏

9.15 难度1

请先思考后再展开

这道题的题意不太清晰
其实就是尽量少去交给命运决定……(少尝试)
答案就是 $\frac{n-尝试数量}{n}$ ,也就是都不是杀手
那么缩点后找入度为0即可
不过如果本来是一个点,那么可以用排除法得出结果,稍微判断一下即可

30 poj3648 Wedding

9.15 难度1

请先思考后再展开

2-sat比较显然
假设新娘在右边,然后左边不能有通奸,直接scc判断即可
那么因为有可能新郎也通奸,导致新娘去左边了,
为了防止这种情况,从新娘到新郎连一条边表示非法性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
const int MAX_N=110000;
typedef long long ll;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
int hou[MAX_N];
struct Edge
{
int y,g;
}e[MAX_N];
int ln;void ins(int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int id,dfn[MAX_N],low[MAX_N];
int cnt,belg[MAX_N];
int sta[MAX_N],top;bool insta[MAX_N];
void tarjan(int x)
{
sta[++top]=x;insta[x]=1;
dfn[x]=low[x]=++id;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(dfn[y]==0) tarjan(y),low[x]=mymin(low[x],low[y]);
else if(insta[y]) low[x]=mymin(low[x],dfn[y]);
}
if(dfn[x]==low[x])
{
cnt++;
while(1)
{
int now=sta[top--];
belg[now]=cnt;
insta[now]=0;
if(now==x) break;
}
}
}
int getid()
{
int t;char c;scanf("%d%c",&t,&c);
return 2*t+(c=='h');//0~2n-1
}
void output(int x) {printf("%d%c ",x/2,x&1?'h':'w');}
bool v[MAX_N];//块的选择状态
void main()
{
while(1)
{
int n,m;scanf("%d%d",&n,&m);
if(n==0 and m==0) break;
ln=0;memset(hou,0,sizeof hou);
ins(0,1);//确保选新郎,否则非法
for(int i=1;i<=m;i++)
{
int a=getid(),b=getid();
ins(a,b^1);ins(b,a^1);
}
cnt=0;top=0;id=0;
memset(dfn,0,sizeof dfn);
for(int i=0;i<=2*(n-1)+1;i++) if(dfn[i]==0) tarjan(i);
memset(v,0,sizeof v);
//反图拓扑序小=>正图拓扑序大=>正图scc编号小
bool bk=0;
for(int i=0;i<=n-1;i++)
{
int fx=belg[i*2],fy=belg[i*2+1];
if(fx==fy) bk=1;
v[mymin(fx,fy)]=1;
}
if(bk) {puts("bad luck");continue;}
for(int i=1;i<=n-1;i++) output(v[belg[2*i]]?2*i+1:2*i);//得出新郎,输出新娘
puts("");
}
}
};
int main()
{
mine::main();
}

31 poj1112 Team Them Up!

9.15 难度2

请先思考后再展开

在本题中,单一的单向边是没有意义的,应转化为双向边
这里注意一点,每个组内部的节点,通过一条边就能互相到达,间接到达不算认识
因为这个直接到达有点麻烦,如果取补图,边的意义就是【不能在相同的组中】
此时成功产生了互斥关系,可以二分图染色,如果不是二分图,直接无解

1
2

32

9.15 难度2

请先思考后再展开
1
2

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/6259.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%