CF #CROC 2016 - Elimination Round D. Robot Rapping Results Report 二分+拓扑排序

75 阅读 0 评论 50 点赞

我是靠谱客的博主热情月亮，最近开发中收集的这篇文章主要介绍CF #CROC 2016 - Elimination Round D. Robot Rapping Results Report 二分+拓扑排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：http://codeforces.com/contest/655/problem/D

大意是给若干对偏序，问最少需要前多少对关系，可以确定所有的大小关系。

解法是二分答案，利用拓扑排序看是否所有关系被唯一确定。即任意一次只能有1个元素入度为0入队。

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <string>
 5 #include <string.h>
 6 #include <stdio.h>
 7 #include <math.h>
 8 #include <queue>
 9 #include <stack>
10 #include <map>
11 #include <set>
12
13 using namespace std;
14
15
16 const int N=123456;
17
18 struct Edge {
19
int to,next;
20 
Edge() {}
21
Edge(int _to,int _nxt):to(_to),next(_nxt) {}
22 } edge[N<<2];
23 int idx=1,head[N];
24 void addedge(int u,int v) {
25
edge[++idx]=Edge(v,head[u]);
26
head[u]=idx;
27 }
28 int in[N],que[N];
29
30 int a[N],b[N];
31
32 bool topoSort(int n,int mid){
33
idx=1;memset(head,0,sizeof head);
34
memset(in,0,sizeof in);
35
for (int i=1;i<=mid;i++) {
36 
addedge(a[i],b[i]);
37
in[b[i]]++;
38 
}
39
int tail=0;
40
for (int i=1;i<=n;i++)
41
if (in[i]==0)
42
que[tail++]=i;
43
if (tail>1) return false;
44
for (int i=0;i<tail;i++){
45
int cnt=0;
46
for (int k=head[que[i]];k;k=edge[k].next){
47
int v=edge[k].to;
48
in[v]--;
49
if (in[v]==0){
50
cnt++;
51
if (cnt>1) return false;
52
que[tail++]=v;
53 
}
54 
}
55 
}
56
return true;
57 }
58
59
60 int main() {
61
int n,m;
62
scanf("%d %d",&n,&m);
63
for (int i=1;i<=m;i++) {
64
scanf("%d %d",a+i,b+i);
65 
}
66
int low=1,high=m,ret=-1;
67
while (low<=high) {
68
int mid=(low+high)>>1;
69
if (topoSort(n,mid)) {
70
ret=mid;
71
high=mid-1;
72 
}
73
else
74
low=mid+1;
75 
}
76
printf("%dn",ret);
77
return 0;
78 }