算法竞赛入门经典 写题笔记（第五章 图论算法与模型2）
生活随笔
收集整理的這篇文章主要介紹了
算法竞赛入门经典 写题笔记（第五章 图论算法与模型2）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
本節(jié)內(nèi)容——
- 2-SAT
- dijstra算法的一些應(yīng)用
- SPFA算法的一些應(yīng)用
例題9 飛機(jī)調(diào)度
有n架飛機(jī)需要著陸。每架飛機(jī)都可以選擇“早著陸"和”晚著陸“兩種方式之一，且必須選擇一種。第i架飛機(jī)的早著陸時(shí)間為\(E_i\)，晚著陸時(shí)間為\(L_I\),不得在其他時(shí)間著陸。現(xiàn)在需要安排這些飛機(jī)的著陸方式，使得整個(gè)著陸計(jì)劃盡量安全。換句話說(shuō)，如果把所有飛機(jī)的實(shí)際著陸時(shí)間按照從早到晚的順序排列，相鄰兩個(gè)著陸時(shí)間間隔的最小值（成為安全間隔）盡量大。
也就是二分這個(gè)時(shí)間，然后判斷該2-SAT是否有解。（因?yàn)檫@個(gè)間隔時(shí)間越小就也可能有合法解，反之越不可能，所以可以二分答案）
構(gòu)圖的時(shí)候，如果兩個(gè)決策（比如說(shuō)\(i_l,j_l\)）間隔小于二分的答案，我們就給\(i_l,j_r\)和\(i_r,j_l\)連有向邊。
然后跑tarjan判斷就行了，如果同一個(gè)飛機(jī)的兩個(gè)決策在一個(gè)強(qiáng)聯(lián)通分量里面，就沒有合法解了。
順便一提，劉汝佳書上寫的那個(gè)做法復(fù)雜度是假的qwq
例題10 宇航員分組
有A，B，C三種任務(wù)要分配給n個(gè)宇航員，其中每個(gè)宇航員恰好要分配一個(gè)任務(wù)。設(shè)所有n個(gè)宇航員的平均年齡為x，只有年齡大于或等于x的宇航員才能分配任務(wù)A；只有年齡嚴(yán)格小于x的宇航員才能分配任務(wù)B，而任務(wù)C沒有限制。有m對(duì)宇航員相互討厭，因此不能分配到統(tǒng)一任務(wù)。現(xiàn)在需要找出一個(gè)滿足上訴所有要求的任務(wù)分配方案。
3-SAT？？？不可能的。我們只要處理一下年齡，對(duì)于每個(gè)宇航員，照樣是2-SAT.
然后就......和上面那題一樣做就行了啊？？
但是為什么會(huì)RE啊......搞不懂......先把代碼貼上，回來(lái)找鍋（咕咕咕）
例題11 機(jī)場(chǎng)快線
機(jī)場(chǎng)快線分為經(jīng)濟(jì)線和商業(yè)線兩種，線路、速度和價(jià)錢都不同。現(xiàn)在你有一張商業(yè)線的車票，可以坐一站商業(yè)線，而其他時(shí)候只能乘坐經(jīng)濟(jì)線。假設(shè)換成時(shí)間忽略不計(jì)，你的任務(wù)是找一條取機(jī)場(chǎng)最快的線路，然后輸出方案。（保證最優(yōu)解唯一）
因?yàn)樯虡I(yè)線只能坐一站，而且數(shù)據(jù)范圍在1000以內(nèi)，所以我們可以枚舉坐的是哪一站。
假設(shè)我們用商業(yè)線車票從車站a坐到b，則從起點(diǎn)到a，從b到終點(diǎn)這兩部分的路線對(duì)于只存在經(jīng)濟(jì)線的圖中一定是最短路。所以我們只需要從起點(diǎn)、終點(diǎn)開始做兩次最短路，記錄下從起點(diǎn)到每個(gè)點(diǎn)x的最短時(shí)間\(f(x)\)和它到終點(diǎn)的最短時(shí)間\(g(x)\)，那么總時(shí)間就是\(f(a)+time(a,b)+g(b)\)。
書上還提到了dij算法的路徑統(tǒng)計(jì)，在這里就簡(jiǎn)單說(shuō)一下吧
枚舉兩點(diǎn)之間的所有最短路：先求出所有點(diǎn)到目標(biāo)點(diǎn)的最短路長(zhǎng)度\(d[i]\),然后從起點(diǎn)開始出發(fā)，只沿著\(d[i]=d[j]+dist(i,j)\)的邊走。
兩點(diǎn)之間的最短路計(jì)數(shù)：令\(f[i]\)表示從i到目標(biāo)點(diǎn)的最短路的條數(shù)，則\(f[i]=\sum f[j] | d[i]=d[j]+dist(i,j)\)（這里書上寫錯(cuò)了）
例題12 林中漫步
對(duì)于一張圖，只沿著滿足如下條件的道路（A,B）走：存在一條從B出發(fā)回家的路徑，比所有從A出發(fā)回家的路徑都短。問不同的回家路徑條數(shù)。
先跑完以家為源點(diǎn)的最短路，然后如果一個(gè)點(diǎn)a的最短路比b的小，那么連邊，這就是一個(gè)DAG了，然后再DP計(jì)個(gè)數(shù)就行了。
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define MAXN 100010 using namespace std; int n,m,t; int head[MAXN<<1],done[MAXN],dis[MAXN],dp[MAXN]; struct Node { int u,d;friend bool operator < (Node x,Node y){return x.d>y.d;} }; struct Edge{int nxt,to,dis;}edge[MAXN<<1]; struct Line{int u,v,w;}line[MAXN<<1]; inline void add(int from,int to,int dis) {edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t; } inline void dij(int x) {priority_queue<Node>q;memset(done,0,sizeof(done));memset(dis,0x3f,sizeof(dis));q.push((Node){x,0});dis[x]=0;while(!q.empty()){int u=q.top().u;q.pop();if(done[u]) continue;done[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(dis[v]>dis[u]+edge[i].dis)dis[v]=dis[u]+edge[i].dis,q.push((Node){v,dis[v]});}} } inline int solve(int x) {if(x==2) return dp[x]=1;int cur_ans=0;for(int i=head[x];i;i=edge[i].nxt){int v=edge[i].to;if(!dp[v]) dp[v]=solve(v);cur_ans+=dp[v];}return cur_ans; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifwhile(scanf("%d%d",&n,&m)==2&&n){memset(head,0,sizeof(head));memset(dp,0,sizeof(dp));t=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&line[i].u,&line[i].v,&line[i].w);add(line[i].u,line[i].v,line[i].w);add(line[i].v,line[i].u,line[i].w);}dij(2);// for(int i=1;i<=n;i++) printf("dis[%d]=%d\n",i,dis[i]);memset(head,0,sizeof(head));t=0;for(int i=1;i<=m;i++){if(dis[line[i].u]>dis[line[i].v]) add(line[i].u,line[i].v,line[i].w);if(dis[line[i].v]>dis[line[i].u]) add(line[i].v,line[i].u,line[i].w);}printf("%d\n",solve(1));}return 0; }最短路樹：用dij算法可以求出單元最短路樹，方法是在發(fā)現(xiàn)\(d[i]+w(i,j)<d[j]\)時(shí)除了更新\(d[j]\)之外還要設(shè)置\(p[j]=i\)。這樣，所有點(diǎn)就形成了一棵樹。
要從起點(diǎn)出發(fā)沿著最短路走到其他任意點(diǎn)，只需要順著樹上的邊走即可。
例題13 戰(zhàn)爭(zhēng)和物流
給出一個(gè)n個(gè)節(jié)點(diǎn)m條邊的無(wú)向圖（n<=100,m<=1000），每條邊上有一個(gè)正權(quán)。令c等于每對(duì)節(jié)點(diǎn)的最短路長(zhǎng)度之和。要求刪除一條邊后使得新的c值c'最大。不聯(lián)通的兩點(diǎn)的最短路長(zhǎng)度視為L(zhǎng)。
在源點(diǎn)確定的情況下，只要最短路樹不被破壞，起點(diǎn)到所有點(diǎn)的距離都不會(huì)發(fā)生改變。換句話說(shuō)，只有刪除最短路樹上的n-1條邊（中的任意條），最短路樹才需要重新計(jì)算。
這樣的話，我們對(duì)于每個(gè)源點(diǎn)，最多只需要求n次而不是m次最短路，時(shí)間復(fù)雜度為\(O(n^2mlogn)\)（dij算法的時(shí)間復(fù)雜度為\(O(mlogn)\)）
例題14 過路費(fèi)（加強(qiáng)版）
運(yùn)送貨物需要繳納過路費(fèi)。進(jìn)入一個(gè)尋裝需要繳納一個(gè)單位的貨物，進(jìn)入一個(gè)城鎮(zhèn)時(shí)，每20個(gè)單位的貨物中就要上繳1個(gè)單位（比如，攜帶70個(gè)單位的貨物進(jìn)入城鎮(zhèn)，需要繳納4個(gè)單位的貨物）。現(xiàn)在給定你一張圖，請(qǐng)找出一條繳納過路費(fèi)最少的路線，并輸出。如果有多條路線，輸出字典序最小的。
逆推的dij算法。令\(d[i]\)表示進(jìn)入節(jié)點(diǎn)i之后，至少需要\(d[i]\)個(gè)單位的貨物，到達(dá)目的地時(shí)貨物數(shù)量才足夠。則每次選擇一個(gè)\(d[i]\)最小的未標(biāo)號(hào)的節(jié)點(diǎn)，更新它的所有前驅(qū)節(jié)點(diǎn)的d值就行了。輸出路徑的時(shí)候根據(jù)d值就可以構(gòu)造出字典序最小的解。
emmmm為什么我把書上的解釋全抄下來(lái)了......因?yàn)槲矣X得寫得確實(shí)比較清晰啊qwq
這個(gè)題我的代碼還是不知道為什么鍋了。。。先敷衍一下放個(gè)maomao的吧......
#include <bits/stdc++.h> using namespace std;#define int long longconst int N = 200 + 5; const int INF = 0x3f3f3f3f3f3f3f3f;vector <int> G[N];int n, p, kase, dis[N], done[N]; char s, t;int get_tot (int w) {int l = 0, r = 1e17;while (l < r) {int mid = (l + r) >> 1;if (mid - ceil ((1.0 * mid) / 20.0) >= w) {r = mid;} else {l = mid + 1;}}return r; }struct HeapNode {int u, d;bool operator < (HeapNode rhs) const {return d > rhs.d; } };priority_queue <HeapNode> q;void solve () {memset (done, 0, sizeof (done));memset (dis, 0x3f, sizeof (dis));dis[(int)t] = isupper (t) ? get_tot (p) : p + 1;q.push ((HeapNode) {t, dis[(int)t]});while (!q.empty ()) {HeapNode now = q.top (); q.pop ();if (done[now.u]) continue;for (int i = 0; i < (int) G[now.u].size (); ++i) {int v = G[now.u][i];int _w = isupper (v) ? get_tot (dis[now.u]) : dis[now.u] + 1;if (dis[v] > _w) {dis[v] = _w;q.push ((HeapNode) {v, dis[v]});} }done[now.u] = true; } }bool cmp (int lhs, int rhs) {return dis[lhs] == dis[rhs] ? lhs < rhs : dis[lhs] < dis[rhs]; }signed main () {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifwhile (cin >> n) {if (n == -1) break;cout << "Case " << ++kase << ":" << endl;for (int i = 0; i < N; ++i) G[i].clear ();for (int i = 1; i <= n; ++i) {static char u, v;cin >> u >> v;G[(int)u].push_back ((int)v);G[(int)v].push_back ((int)u);}cin >> p >> s >> t;solve ();int min_dis = 0x7fffffffffffffffll;for (int i = 0; i < (int)G[(int)s].size (); ++i) {int v = G[(int)s][i];min_dis = min (min_dis, dis[v]);}for (int i = 0; i < N; ++i) {if (!G[i].empty ()) {sort (G[i].begin (), G[i].end (), cmp);}}if (s == t) {cout << p << endl;cout << (char) t << endl;continue;}cout << min_dis << endl;int now = s; cout << (char) s << "-";while (now != t) {now = G[now][0];cout << (char) now; if (now != t) cout << "-";} cout << endl;} }例題15 在環(huán)中
給定一個(gè)n個(gè)點(diǎn)m條邊（n<=50）的加權(quán)有向圖，求平均權(quán)值最小的回路。輸入沒有自環(huán)。
二分答案。假設(shè)存在一個(gè)包含k條邊的回路，回路上各條邊的權(quán)值為\(w_1,w_2,...,w_k\)，那么平均值小于mid意味著\((w_1-mid)+(w_2-mid)+...+(w_k-mid)<0\)，那么就直接給每條邊減去mid,然后用SPFA判斷一下是否有負(fù)環(huán)就行了。
注意小數(shù)二分的時(shí)候精度不要取太高......常數(shù)太大會(huì)T的.......
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define MAXN 110 #define eps 1e-7 using namespace std; int n,m,t,T,kase; int head[MAXN],done[MAXN],cnt[MAXN]; double dis[MAXN]; struct Line{int u,v;double w;}line[MAXN*MAXN]; struct Edge{int nxt,to;double dis;}edge[MAXN*MAXN]; inline void add(int from,int to,double dis) {edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t; } inline bool spfa(int x) {queue<int>q;for(int i=0;i<=n;i++) dis[i]=1e9,done[i]=cnt[i]=0;q.push(x);done[x]=1;dis[x]=0;while(!q.empty()){int u=q.front();q.pop();done[u]=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(dis[v]>dis[u]+edge[i].dis){dis[v]=dis[u]+edge[i].dis;if(!done[v]){done[v]=1;q.push(v);if(++cnt[v]>=n) return false; }}}}return true; } inline bool check(double x) {bool flag=false;for(int i=1;i<=n;i++)for(int j=head[i];j;j=edge[j].nxt)edge[j].dis-=x;for(int i=1;i<=n;i++)if(!spfa(i)==true) flag=true;for(int i=1;i<=n;i++)for(int j=head[i];j;j=edge[j].nxt)edge[j].dis+=x;// puts("oh no");return flag; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifscanf("%d",&T);while(T--){memset(head,0,sizeof(head));t=0;scanf("%d%d",&n,&m);double l=1e9,r=0.0;for(int i=1;i<=m;i++){scanf("%d%d%lf",&line[i].u,&line[i].v,&line[i].w);add(line[i].u,line[i].v,line[i].w);r=max(r,line[i].w);l=min(l,line[i].w);}printf("Case #%d: ",++kase);if(!check(r+1)) printf("No cycle found.\n");else{while(l+eps<r){double mid=(l+r)/2.0;// printf("l=%.2lf r=%.2lf mid=%.2lf\n",l,r,mid);if(check(mid)) r=mid;else l=mid;}printf("%.2lf\n",r);}}return 0; }例題16 Halum操作
給定一個(gè)有向圖，每條邊都有一個(gè)權(quán)值。每次你可以選擇一個(gè)節(jié)點(diǎn)v和一個(gè)整數(shù)d，把所有以v為終點(diǎn)的邊的權(quán)值減小d，把所有以v為起點(diǎn)的邊的權(quán)值增加d，最后要讓所有邊權(quán)的最小值為正且盡量大。
因?yàn)椴煌牟僮骰ゲ挥绊?#xff0c;所以可以按照任意順序?qū)嵤┻@些操作。另外，對(duì)于同一個(gè)節(jié)點(diǎn)的多次操作也可以合并，所以我們可以令sum(u)表示作用于節(jié)點(diǎn)u之上的所有d之和。然后二分答案x，問題轉(zhuǎn)化成為是否可以讓所有操作完成后每條邊的權(quán)值均不小于x。對(duì)于邊a->b，操作完之后應(yīng)該是\(w(a,b)+sum[a]-sum[b] \ge x\)，也就是\(sum[b]-sum[a]<=w(a,b)-x\)。這樣，就是一個(gè)差分約束系統(tǒng)了，我們連a到b，權(quán)值為\(w(a,b)-x\)的邊。然后用負(fù)環(huán)來(lái)判斷這個(gè)差分約束系統(tǒng)是否有解。
對(duì)了，書上的翻譯感覺有問題。依AC代碼來(lái)看，應(yīng)該是讓所有邊的最小值為正且盡量大......
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define MAXN 510 using namespace std; int n,m,t; int head[MAXN],done[MAXN],dis[MAXN],cnt[MAXN]; struct Edge{int nxt,to,dis;}edge[3000]; struct Line{int u,v,w;}line[3000]; inline void add(int from,int to,int dis) {edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t; } inline bool spfa() {queue<int>q;for(int i=1;i<=n;i++)q.push(i),done[i]=1,dis[i]=0x3f3f3f3f,cnt[i]=0;while(!q.empty()){int u=q.front();q.pop();done[u]=0;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(dis[v]>dis[u]+edge[i].dis){dis[v]=dis[u]+edge[i].dis;if(!done[v]){done[v]=1;cnt[v]++;q.push(v);if(cnt[v]>=n) return false;}}}}return true; } inline bool check(int x) {bool flag=false;for(int i=1;i<=n;i++)for(int j=head[i];j;j=edge[j].nxt)edge[j].dis-=x;if(spfa()) flag=true;for(int i=1;i<=n;i++)for(int j=head[i];j;j=edge[j].nxt)edge[j].dis+=x;return flag; } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifwhile(scanf("%d%d",&n,&m)!=EOF){memset(head,0,sizeof(head));t=0;int l=0,r=-0x3f3f3f3f,ans;for(int i=1;i<=m;i++){scanf("%d%d%d",&line[i].u,&line[i].v,&line[i].w);add(line[i].u,line[i].v,line[i].w);r=max(r,line[i].w);}if(!check(1)) {printf("No Solution\n");continue;}else if(check(r)) {printf("Infinite\n");continue;}while(l<=r) {int mid=(l+r)>>1;if(check(mid)) ans=mid,l=mid+1;else r=mid-1;}printf("%d\n",ans);}return 0; }例題17 蒸汽式壓路機(jī)
翻譯還是去看書吧.......（反正我大概也是每次都抄一遍）
拆點(diǎn)的最短路，因?yàn)橐粋€(gè)位置表示的狀態(tài)不一樣，所以我們要拆點(diǎn)來(lái)分別代表這些狀態(tài)
把每個(gè)點(diǎn)\((r,c)\)拆成8個(gè)點(diǎn)\((r,c,dir,double)\)，分別表示上一步從上下左右的哪個(gè)方向(dir)移動(dòng)到這個(gè)點(diǎn)，以及移動(dòng)到這個(gè)點(diǎn)的這條邊的權(quán)值是否已經(jīng)加倍(doubled)
題解也還是去看書吧.......（反正圖我也是畫不出來(lái)的......）
例題18 低價(jià)空中旅行
給你一些票，每張聯(lián)票上標(biāo)明上面以此經(jīng)過的站，以及本票的價(jià)錢。必須從頭開始坐，可以在中途任何一站下飛機(jī)，下飛機(jī)后票上繳，不可以再次使用本票。
現(xiàn)在給出一些行程單，問如何買票能使得總花費(fèi)最小（同一種票能夠買多張）。輸入保證行程總是可行的，行程單上的城市必須按照順序到達(dá)，但是中間可以經(jīng)過一些輔助城市。
輸入保證每組數(shù)據(jù)最多包含20種聯(lián)票和20個(gè)行程單，聯(lián)票或者行程單上的相鄰城市保證不同。票和行程單都從1開始編號(hào)。
例題19 動(dòng)物園大逃亡
平面圖轉(zhuǎn)對(duì)偶圖，用最短路求最小割。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define S 0 #define T tot+1 #define MAXN 5000010 using namespace std; int n,m,t,cur,kase,tot; int dis[MAXN],done[MAXN],head[MAXN],id[1010][1010][2]; struct Node {int u,d;friend bool operator <(struct Node x,struct Node y){return x.d>y.d;} }; struct Edge{int nxt,to,dis;}edge[MAXN<<1]; inline void add(int from,int to,int dis) {// printf("[%d %d] %d\n",from,to,dis);edge[++t].nxt=head[from],edge[t].to=to,edge[t].dis=dis,head[from]=t;edge[++t].nxt=head[to],edge[t].to=from,edge[t].dis=dis,head[to]=t; } inline void dij() {priority_queue<Node>q;memset(dis,0x3f,sizeof(dis));memset(done,0,sizeof(done));q.push((Node){S,0});dis[S]=0;while(!q.empty()){int u=q.top().u; q.pop();if(done[u]) continue;done[u]=1;for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].to;if(dis[u]+edge[i].dis<dis[v])dis[v]=dis[u]+edge[i].dis,q.push((Node){v,dis[v]});}} } int main() {#ifndef ONLINE_JUDGEfreopen("ce.in","r",stdin);#endifwhile(scanf("%d%d",&n,&m)==2&&n+m){memset(head,0,sizeof(head));t=tot=0;n--,m--;// printf("n=%d m=%d\n",n,m);for(int i=0;i<=n+1;i++)for(int j=0;j<=m+1;j++)for(int k=0;k<=1;k++)id[i][j][k]=++tot;for(int i=1;i<=n+1;i++){int x;for(int j=1;j<=m;j++){scanf("%d",&x);add(id[i][j][1],id[i-1][j][0],x);}}for(int i=1;i<=n;i++){int x;for(int j=1;j<=m+1;j++){scanf("%d",&x);add(id[i][j][0],id[i][j-1][1],x);}}for(int i=1;i<=n;i++){int x;for(int j=1;j<=m;j++){scanf("%d",&x);add(id[i][j][1],id[i][j][0],x);}}for(int i=1;i<=n;i++) add(S,id[i][0][1],0);for(int j=1;j<=m;j++) add(S,id[n+1][j][1],0);for(int j=1;j<=m;j++) add(id[0][j][0],T,0);for(int i=1;i<=n;i++) add(id[i][m+1][0],T,0);dij();printf("Case %d: Minimum = %d\n",++kase,dis[T]);// printf("%d\n",dis[T]);}return 0; }轉(zhuǎn)載于:https://www.cnblogs.com/fengxunling/p/10851094.html
總結(jié)
以上是生活随笔為你收集整理的算法竞赛入门经典 写题笔记（第五章 图论算法与模型2）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 新宝股份有限公司待遇怎么样 找工作的可以
- 下一篇： 股票是有价证券吗