POJ3687 Labeling Balls（拓扑排序贪心+Floyd）

题目是要给n个重量1到n的球编号，有一些约束条件：编号A的球重量要小于编号B的重量，最后就是要输出字典序最小的从1到n各个编号的球的重量。

正向拓扑排序，取最小编号给最小编号是不行的，不举出个例子真的很难理解= =比如这个数据：

1

4 2

4 1

3 2

正确答案是2 4 3 1，会得到的错误答案是4 2 1 3。

一开始我是用了贪心的做法，每次选未安排重量的最小的编号，安排给它尽量小的重量。某个编号能得到的最小的重量的计算是这样的：

计算出约束中重量要小于此编号的编号个数，记为k，这个可以先用Floyd预处理出任意两点间的连通性然后遍历一遍统计
因而这个编号能得到的最小重量就是第k个还没被用的重量
这时候还要回溯把所有约束中重量要小于到这个编号的编号给他们安排上k-1个重量

见代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 bool map[222][222];
 7 int n,m;
 8 bool floyd(){
 9     for(int k=1; k<=n; ++k){
10         for(int i=1; i<=n; ++i){
11             for(int j=1; j<=n; ++j){
12                 map[i][j]|=(map[i][k]&map[k][j]);
13             }
14         }
15     }
16     for(int i=1; i<=n; ++i) if(map[i][i]) return 0;
17     return 1;
18 }
19 bool vis[222];
20 int getk(int k){
21     for(int i=1; i<=n; ++i){
22         if(!vis[i]) if(--k==0) return i;
23     }
24     return 0;
25 }
26 int d[222];
27 void dfs(int u){
28     if(d[u]) return;
29     int cnt=0;
30     for(int v=1; v<=n; ++v){
31         if(map[v][u] && !d[v]) ++cnt;
32     }
33     d[u]=getk(cnt+1);
34     vis[d[u]]=1;
35     for(int v=1; v<=n ;++v){
36         if(map[v][u]) dfs(v);
37     }
38 }
39 int main(){
40     int t,a,b;
41     scanf("%d",&t);
42     while(t--){
43         memset(d,0,sizeof(d));
44         memset(map,0,sizeof(map));
45         memset(vis,0,sizeof(vis));
46         scanf("%d%d",&n,&m);
47         while(m--){
48             scanf("%d%d",&a,&b);
49             map[a][b]=1;
50         }
51         if(!floyd()){
52             puts("-1");
53             continue;
54         }
55         for(int i=1; i<=n; ++i){
56             dfs(i);
57             printf("%d ",d[i]);
58         }
59         putchar('
');
60     }
61     return 0;
62 }

View Code

事实上这题正解是反着进行拓扑排序，就是逆图中进行拓扑排序，取最大编号给最大重量。

正确性我是这么理解的：

当前安排的编号是x，有两个入度0的结点a和b，且a<b，按算法是给b球编号x。

反证法，假设给a球编号x能更优，那么

Case b: ...[ ]...[ ]...[x] [ ]... （weight[b]=x）

Case a: ...[y]...[x]...[ ] [ ]... （weight[a]=x）

在后面编号的安排中，就存在一个小于x的编号y被安排在了(Case a)中a的前面，且(Case b)不能做到字典序更小的。但这是不存在的，因为(Case b)马上就能把x-1这个编号安排在a位置，即weight[a]=x-1，这样(Case a)能做的(Case b)也能做了，且(Case b)编号还更小。

所以，选择b编号x比a编号x更优。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 using namespace std;
 5 #define MAXN 222
 6 #define MAXM 44444
 7 struct Edge{
 8     int u,v,next;
 9 }edge[MAXM];
10 int NE,head[MAXN];
11 void addEdge(int u,int v){
12     edge[NE].u=u; edge[NE].v=v; edge[NE].next=head[u];
13     head[u]=NE++;
14 }
15 int deg[MAXN],size[MAXN];
16 bool toposort(int n){
17     priority_queue<int> que;
18     for(int i=1; i<=n; ++i){
19         if(deg[i]==0) que.push(i);
20     }
21     for(int k=n; k>=1; --k){
22         if(que.empty()) return 0;
23         int u=que.top(); que.pop();
24         size[u]=k;
25         for(int i=head[u]; i!=-1; i=edge[i].next){
26             int v=edge[i].v;
27             if(--deg[v]==0) que.push(v);
28         }
29     }
30     return 1;
31 }
32 int main(){
33     int t,n,m,a,b;
34     scanf("%d",&t);
35     while(t--){
36         NE=0;
37         memset(head,-1,sizeof(head));
38         memset(deg,0,sizeof(deg));
39         scanf("%d%d",&n,&m);
40         while(m--){
41             scanf("%d%d",&a,&b);
42             addEdge(b,a);
43             ++deg[a];
44         }
45         if(toposort(n)){
46             for(int i=1; i<=n; ++i) printf("%d ",size[i]);
47             putchar('
');
48         }else puts("-1");
49     }
50     return 0;
51 }

View Code