題目描述

輸入

第一行：點的個數，如果點個數是n，他們的編號為0 ~ n-1

余下的行：每行代表一條邊，如“0 2”代表頂點0和頂點2有一條邊 (一條邊只出現一次，如出現“0 2”則不會出現“2 0”)

輸出

這次需要大家先輸出一個字符串，它是“我已閱讀關于抄襲的說明”的漢語拼音.輸出此行的提交我們將認為已經完全閱讀并了解了“關于抄襲的說明”公告.

所有的割點和所有的橋，先輸出割點再輸出橋

割點按編號升序排列，橋按邊的升序排列，如“0 2”小于“0 3”，“1 5”小于“2 3”（邊的輸出和排列總是把小頂點放前面，所以輸出總是“0 2”而非“2 0”）

5
1 2
1 3
2 4
0 1
0 2

wo yi yue du guan yu chao xi de shuo ming
1
2
1 3
2 4

提示

兩個算法的偽代碼書上都有了，就不多說了。

這個題比較坑的地方是空間復雜度，開始保存圖一直使用的set<int>，一直不過，改成vector<int>就過了

本題中，為了節省空間，我盡量使用了new，在染色節點的時候，我直接使用了discovertime來表示，當discovertime==0時表示節點未訪問，discovertime<0表示正在訪問，discovertime>0時表示訪問結束。所以在DFS剛訪問節點設置discovertime時，我將discovertime設置為-time，結束時去絕對值。

答案

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;//找割點
void DFS_find_cutvertex(vector<int>* g, int point, int time, pair<int, int>* times,vector<int> & result,int& treenum,int parent) {++time;//在訪問節點是，將back設為當前時間times[point].second = time * -1;times[point].first = time;//節點染成灰色for (auto i = g[point].begin(); i!= g[point].end(); i++) {//到此時，此時i表示需要遍歷的下一個鄰居節點int y = *i;if (times[*i].second == 0) {if (point == 0) treenum++;DFS_find_cutvertex(g, *i, time, times,result,treenum,point);//判斷是否為割點if (times[*i].first >= abs(times[point].second) && point != 0)result.emplace_back(point);times[point].first = min(times[point].first, times[*i].first);}else {//正在被訪問，這能代表BF的邊？if (times[*i].second < 0 && *i != parent) {times[point].first = min(times[point].first, abs(times[*i].second));}}}//節點染成黑色times[point].second = abs(times[point].second);
}//找橋，對尋找割點的程序簡單修改
void DFS_find_bridge(vector<int>* g, int point, int time, pair<int, int>* times, vector<pair<int,int>> & result,int parent) {++time;//當discovertime為負數時，表示正在被訪問times[point].second = time * -1;times[point].first = time;for (auto i = g[point].begin(); i != g[point].end(); i++) {if (times[*i].second == 0) {DFS_find_bridge(g, *i, time, times, result,point);times[point].first = min(times[point].first, times[*i].first);if (times[*i].first > abs(times[point].second)) {//保持結果中的邊小的點在前if(point < *i) result.emplace_back(pair<int, int>(point, *i));else result.emplace_back(pair<int, int>(*i,point));}}else {if (times[*i].second < 0 && *i != parent) {times[point].first = min(times[point].first, abs(times[*i].second));}}}//節點染成黑色times[point].second =abs(times[point].second);
}int main()
{int point_num = 0;cin >> point_num;//times的first和second用來存放尋找割點時保存的back值和discovertimepair<int, int>* times = new pair<int, int>[point_num];//每個點能到達的其他點vector<int>* g = new vector<int>[point_num];int in = 0;int out = 0;while (cin >> in && cin >> out) {g[in].emplace_back(out);g[out].emplace_back(in);}//DFS尋找割點int time = 0;vector<int> result;int treenum = 0;DFS_find_cutvertex(g,0,time, times, result,treenum,-1);if (treenum >= 2)result.emplace_back(0);sort(result.begin(),result.end());//將節點全部染成白色.時間重置for (auto i = 0; i < point_num; i++) {times[i].first = 0;times[i].second = 0;}    //DFS尋找橋int time2 = 0;vector<pair<int,int>> result2;DFS_find_bridge(g, 0, time2, times, result2, -1);sort(result2.begin(), result2.end());cout << "wo yi yue du guan yu chao xi de shuo ming" << endl;for (auto i = 0 ;i<result.size();i++)cout << int(result[i]) << endl;for (auto i = 0; i < result2.size(); i++) {cout << int(result2[i].first) << " " << int(result2[i].second) << endl;}delete []times;delete []g;return 0;
}

?

題目描述

請大家在做oj題之前，仔細閱讀關于抄襲的說明http://www.bigoh.net/JudgeOnline/.

算法助教實在是太忙了，每天有n個事情要做，但他覺得自己一件一件的做實在是太蠢了，所以想找一些班上的同學來幫忙一塊做這些事。

在分配任務的過程中他發現，這n個任務中有一些任務的開始需要依賴另一些任務的完成，例如，當只有先批改完算法作業（記為事件A），才能給大家登記作業成績（記為事件B），這時我們就可稱事件B依賴于事件A。機智的他利用了算法課上的知識，采用有向圖中的節點來表示這些事件，并且利用圖中的邊來表示這些事件的依賴關系，例如，當事件B依賴于事件A時，圖中就存在一條由B指向A的邊。助教還對這樣的有向圖進行了升級，用節點的權值表示完成每個事件所需要的時間。

然而，隨后他發現，由于圖中依賴關系的存在，即使他利用龐大的關系網能找來無窮多個同學幫他做這些事，完成所有事件的最短時間也是確定的。那么問題來了，助教每天要花多少時間來處理這n個事情呢？這時，助教想起了算法課上學到的關鍵路徑的定義似乎能夠幫他解決這個問題。聰明的同學們，你們能告訴助教他即使找到幫手，每天做完這n個事情最短也需要花多長時間嗎？

（善良的助教已經幫你們把這些事情建模成有向圖，如輸入所示。）

輸入

第一行為圖中的頂點個數n

第二行至第n+1行為每個頂點代表的事件編號（事件編號為1至n）及完成該事件所需的時間。 如，“1 50”代表完成事件1需要50個單位時間。

余下的行中，每一行表示一個依賴關系，例如，“1 3” 表示事件1的完成依賴于事件3的完成。

輸出

這次依舊需要大家輸出一行字符串，它還是“我已閱讀關于抄襲的說明”的英文翻譯，即："I have read the rules about?plagiarism punishment"。輸出此行的提交我們將認為已經完全閱讀并了解了“關于抄襲的說明”公告并同意關于抄襲的懲罰措施。

第二行輸出完成所有這n個任務所需最短的執行時間。

9
1 10
2 6
3 5
4 1
5 2
6 3
7 4
8 9
9 1
1 9
2 1
2 8
3 5
3 6
3 7
4 2
4 3
5 9
6 9
7 9
8 9

I have read the rules about plagiarism punishment
18

提示

如果這些事情出現了循環依賴，則助教永遠也不可能做完這些事（好慘 TAT）。所以你可以大膽假定，助教要做的這些事情中并不存在循環依賴，也就是說，輸入的圖一定是一個有向無環圖。

答案

?算法同樣在書上有，就不多說了。

這里需要注意的就是在DFS上需要加wapper，遍歷每個節點，找出最大的最早結束時間，注意，在遍歷完一個節點后，不要清除visited和時間內容，這樣遍歷下一個節點時能減少工作量。

具體各對象的實現就看代碼吧

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;//g表示圖，point表示遍歷開始節點，times表示各點最早開始結束時間，visited表示節點訪問狀態,result表示最大的最早結束時間
void DFS_critical_path(vector<int>* g, int point, pair<int, int>* times, vector<int>& visited, vector<int>& cost) {visited[point] = 1;times[point].first = 0;for (auto i = g[point].begin(); i != g[point].end(); i++) {if (visited[*i] == 0) {DFS_critical_path(g, *i, times,visited,cost);if (times[*i].second >= times[point].first) {times[point].first = times[*i].second;}}else {if (times[*i].second >= times[point].first) {times[point].first = times[*i].second;}}}//節點染成黑色times[point].second = times[point].first + cost[point];visited[point] = 2;
}int main() 
{int point_num = 10;cin >> point_num;vector<int> cost(point_num,0);int num = 0;int c = 0;//v[i].first表示最早開始時間，v[i].second表示最早結束時間pair<int, int>* times = new pair<int, int>[point_num];//visited[i] == 0表示節點未訪問，visited == 1 表示節點正在訪問，visited == 2表示訪問結束vector<int> visited(point_num, 0);////path[i] == 0表示i不是關鍵路徑，path[i] == 1表示i是關鍵路徑//vector<int> path(point_num, 0);//獲取每個事件的花費for (int i = 0; i < point_num; i++) {cin >> num;cin >> c;cost[i] = c;}//將A依賴于B表示成圖中有B到A的單向邊，g[i]表示點i能到達的所有點vector<int>* g = new vector<int>[point_num];while (cin >> num && cin >> c) {//輸入是從1開始，但數組索引是從0開始g[num-1].emplace_back(c-1);}/*cost = {10,6,5,1,2,3,4,9,1,20};g[0] = {8};g[1] = {0,7};g[2] = {4,5,6};g[3] = {1,2};g[4] = {8};g[5] = {8};g[6] = {8};g[7] = {8};g[8] = {};g[9] = { 7 };begin[3] = 1;begin[9] = 1;*///DFS遍歷,從所有節點都做一遍DFS，找出最大的最晚結束時間int result = 0;for (int i = 0; i < point_num; i++) {DFS_critical_path(g, i, times, visited, cost);if (times[i].second > result)result = times[i].second;}cout << "I have read the rules about plagiarism punishment" << endl;cout << result << endl;delete[]times;delete[]g;
}

?

轉載于:https://www.cnblogs.com/likaiming/p/9053405.html

總結

以上是生活随笔為你收集整理的南大算法设计与分析课程OJ答案代码（5）--割点与桥和任务调度问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。