暑假集训Day18 G (拓扑排序)

本文主要是介绍暑假集训Day18 G (拓扑排序)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目链接在这里：Problem - G - Codeforces

这也是一道非常巧妙的拓扑排序，本来还以为是一道贪心，后来看了题解大呼牛逼。

我们在自己模拟的时候发现了，无论两种动物怎么交换，如果前面有一种动物跟他不是朋友的话，他一定不能换到这种动物的前面，也就是说，当两者非朋友关系的话，最终他们的相对位置是不变的。这就可以利用拓扑排序的方法去解决。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 const int MAX=305;
 4 const int MAX2=1e5+5;
 5 int l,s,n,last[MAX],tot,in[MAX2];
 6 int a[MAX][MAX];
 7 string ss[MAX2];
 8 int head[MAX2],adj[20000005],nxt[20000005];
 9 map <string,int> p;
10 struct Node{
11     int no,pos;
12     bool operator <(const Node &tt) const {
13         return no>tt.no;
14     }
15 }stu[MAX2];
16 bool cmp(string x,string y){return x<y;}
17 void addedge(int u,int v){
18     tot++;
19     adj[tot]=v;
20     nxt[tot]=head[u];
21     head[u]=tot;
22 }
23 void topu(){
24     int i,j;
25     priority_queue <Node> q;
26     while (!q.empty()) q.pop();
27     for (i=1;i<=n;i++)
28         if (in[i]==0){
29             q.push(stu[i]);
30             //cout<<ss[stu[i].no]<<endl;
31         }
32     while (!q.empty()){
33         Node zt=q.top();q.pop();
34         cout<<ss[zt.no]<<' ';
35         for (i=head[zt.pos];i!=-1;i=nxt[i]){
36             in[adj[i]]--;
37             if (in[adj[i]]==0)
38                 q.push(stu[adj[i]]);
39         }
40     }
41 }
42 int main(){
43     freopen ("g.in","r",stdin);
44     freopen ("g.out","w",stdout);
45     int i,j;string x,y;
46     ios::sync_with_stdio(false);
47     cin>>s>>l>>n;
48     for (i=1;i<=s;i++)
49         cin>>ss[i];
50     sort(ss+1,ss+s+1);
51     for (i=1;i<=s;i++) p[ss[i]]=i;
52     for (i=1;i<=l;i++){
53         cin>>x>>y;
54         a[p[x]][p[y]]=a[p[y]][p[x]]=1;
55     }
56     memset(last,-1,sizeof(last));
57     memset(head,-1,sizeof(head));
58     for (i=1;i<=n;i++){
59         cin>>x;
60         stu[i].pos=i;stu[i].no=p[x];
61         for (j=1;j<=s;j++){
62             if (last[j]==-1 || a[j][p[x]]) continue;
63             addedge(last[j],i);
64             in[i]++;
65         }
66         last[p[x]]=i;
67     }
68     topu();
69     return 0;
70 }

这篇关于暑假集训Day18 G (拓扑排序)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！