一本通 3.4.6 拓扑排序

1352：【例4-13】奖金

【题目描述】

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

【题目分析】

如果a的奖金比b的奖金多，让b指向a，a的入度加1,使用广度优先搜索进行拓扑排序的查找，如果没有入度为0的点则不能找到答案，对拓扑输出点进行计数，不等于n也不能找到答案，初始化入度为0的点奖金为100，后续的拓展点奖金都比前面的点大1，队列弹出时将奖金加和，最后的结果为和。

【代码实现】

#include <bits/stdc++.h>using namespace std;struct node {int x, money;
};vector<node> p[10005];
int indeg[10005];
queue<node> que;int main() {//input dataint m, n;cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;p[y].push_back({x, 0});indeg[x]++;}for (int i = 1; i <= n; i++) {if (indeg[i] == 0)que.push({i, 100});}if (que.empty()) {cout << "Poor Xed" << endl;return 0;}int cnt = 0, sum = 0;while (!que.empty()) {node fa = que.front();que.pop();for (auto e : p[fa.x]) {if (--indeg[e.x] == 0) que.push({e.x, fa.money + 1});}cnt++;sum += fa.money;	}if (cnt != n) cout << "Poor Xed" << endl;else cout << sum << endl;return 0;
}

1395：烦人的幻灯片(slides)

【题目描述】

李教授将于今天下午作一次非常重要的演讲。不幸的事他不是一个非常爱整洁的人，他把自己演讲要用的幻灯片随便堆在了一起。因此，演讲之前他不得不去整理这些幻灯片。作为一个讲求效率的学者，他希望尽可能简单地完成它。教授这次演讲一共要用n张幻灯片（n<=26），这n张幻灯片按照演讲要使用的顺序已经用数字1~n编了号。因为幻灯片是透明的，所以我们不能一下子看清每一个数字所对应的幻灯片。

现在我们用大写字母A,B,C……再次把幻灯片依次编号。你的任务是编写一个程序，把幻灯片的数字编号和字母编号对应起来，显然这种对应应该是唯一的；若出现多种对应的情况或是某些数字编号和字母编号对应不起来，我们称对应是无法实现的。

【题目分析】

题目分析：根据幻灯片的坐标范围可以确定每一张幻灯片的可能多个位置，本题的实质是求解一种可能的组合。

样例解释：A可能为1 2 4，B可能为1 3，C可能为1 2 3，D可能为3，首先D的入度为1，去掉3以后，B的入度为1，再去掉1以后，C的入度为1，再去掉2，A的入度为1
算法实现：vis[]标记有效的数值编号，encode[]记录字母对应的编号，point[]记录每个字母指向的可能数值编号，统计出度为1的字母，找到该字母对应的编号记录到encode中，并将对应数字编号标记为无效，检查所有其他字母去掉该数字编号的入度是否为1，依次循环，统计循环次数是否为n，不为n说明无法确定顺序

【代码实现】

#include <bits/stdc++.h>using namespace std;bool vis1[30], vis2[30];
int encode[30];
int indeg[30];
vector<int> p[30];struct node {int xmin, xmax, ymin, ymax;
} huan[30];int main() {//input dataint n;cin >> n;for (int i = 1; i <= n; i++) {cin >> huan[i].xmin >> huan[i].xmax >> huan[i].ymin >> huan[i].ymax;}for (int j = 1; j <= n; j++) {int x, y;cin >> x >> y;for (int i = 1; i <= n; i++) {if (x >= huan[i].xmin && x <= huan[i].xmax && y >= huan[i].ymin && y <= huan[i].ymax)p[i].push_back(j), indeg[i]++;}}int cnt = 0;for (int j = 1; j <= n; j++) {for (int i = 1; i <= n; i++) {if (indeg[i] == 1) {for (auto e : p[i])if (vis1[e] == 0) encode[i] = e, vis1[e] = 1, vis2[i] = 1, cnt++;}}memset(indeg, 0, sizeof(indeg));for (int i = 1; i <= n; i++) {if (vis2[i] == 1) continue;for (auto e : p[i]) {if (vis1[e] == 0) indeg[i]++;}}}if (cnt != n) cout << "None" << endl;else {char c = 'A';for (int i = 1; i <= n; i++) {printf("%c %d\\n", c + i - 1, encode[i]);}}return 0;
}

1396：病毒(virus)

【题目描述】

有一天，小y突然发现自己的计算机感染了一种病毒！还好，小y发现这种病毒很弱，只是会把文档中的所有字母替换成其它字母，但并不改变顺序，也不会增加和删除字母。

现在怎么恢复原来的文档呢！小y很聪明，他在其他没有感染病毒的机器上，生成了一个由若干单词构成的字典，字典中的单词是按照字母顺序排列的，他把这个文件拷贝到自己的机器里，故意让它感染上病毒，他想利用这个字典文件原来的有序性，找到病毒替换字母的规律，再用来恢复其它文档。

现在你的任务是：告诉你被病毒感染了的字典，要你恢复一个字母串。

【题目分析】

因为这k个字符串原本是按字典序排列的，所以是有序的；被病毒感染只会改变原来字符串的样子，但并不会影响原来的排序！
所以我们可以根据这k个字符串得出原字符x和感染后的字符y之间的对应关系！（可以理解为一一对应的映射关系）
怎么找到这种映射关系？
这里我想到的做法是：双层循环+逐位查询+拓扑排序
说白点就是先模拟字典序排序的过程：如果两个字符串的第i位相等，则判断第i+1位，直到其中一个字符串完结
在这个过程中我们找到一个两个字符不同的位置，就进行连边和入度累加的操作，之后使用拓扑排序便能得到映射关系
怎么想到的拓扑排序？
先通过模拟字典序排序过程，我们可以得到如下的字符大小序列：c<e<d<a<b
 和 e<a那么映射关系即：c−>a,e−>b,d−>c,a−>d,b−>e
（注意箭头前的是被感染后的字符，箭头后的是原始字符）c<e<d<a<b这个即是拓扑序列！然后根据这个拓扑序列我们就能够找到映射关系！

【代码实现】

#include <bits/stdc++.h>
using namespace std;
int n,tot;
int f[30],G[30][30],v[30],res[30],h[30];
//f记录入度，G记录前后，v记录是否入队，res中转，h记录对应顺序
string s[50010];
stack<int> r;
int main()
{memset(f,0x3f,sizeof(f));cin>>n;for(int i=1;i<=n;i++) cin>>s[i];for(int i=1;i<n;i++){if(s[i]==s[i+1]) //完全相同，下一个continue;if(s[i+1].find(s[i])==0) //后一个包含前一个，没有比较的意义continue;if(s[i].find(s[i+1])==0){//前一个包含后一个，字典错误（与上一个相反）puts("0"); return 0; }int x=0;while(s[i][x]==s[i+1][x]) //寻找不同字母x++;int a=s[i][x]-'a'+1,b=s[i+1][x]-'a'+1;if(G[b][a]){ //这里a在b前，而之前b在a前，前后矛盾，字典错误，结束puts("0"); return 0; }G[a][b]=1;//存储if(!v[a]) v[a]=1,f[a]=0;if(!v[b]) v[b]=1,f[b]=1;else f[b]++;//入度加一}memset(v,0,sizeof(v));for(int i=1;i<30;i++) if(!f[i]) r.push(i),v[i]=1;while(r.size()) {//拓扑排序int x=r.top(); r.pop();res[++tot]=x;//记录当前for(int i=1;i<30;i++) {if(G[x][i]) f[i]--;//入度减一if(!f[i]&&!v[i]) r.push(i),v[i]=1;}}for(int i=1;i<=tot;i++) h[res[i]]=i;string que,ans; //que是被感染的字符串，ans是答案cin>>que;for(int i=0;i<que.length();i++) {if(!h[que[i]-'a'+1]){//字典不完整，找不到对应字符puts("0"); return 0;}ans+=(char)(h[que[i]-'a'+1]+'a'-1);//记录答案}cout<<ans<<endl;return 0;
}