算法競賽入門經(jīng)典寫題筆記（第五章圖論算法與模型2）

印度阿三17 2019-05-12

展開全文

本節(jié)內(nèi)容——

2-SAT
dijstra算法的一些應用
SPFA算法的一些應用

例題9 飛機調(diào)度

有n架飛機需要著陸。每架飛機都可以選擇“早著陸"和”晚著陸“兩種方式之一，且必須選擇一種。第i架飛機的早著陸時間為\(E_i\)，晚著陸時間為\(L_I\),不得在其他時間著陸。現(xiàn)在需要安排這些飛機的著陸方式，使得整個著陸計劃盡量安全。換句話說，如果把所有飛機的實際著陸時間按照從早到晚的順序排列，相鄰兩個著陸時間間隔的最小值（成為安全間隔）盡量大。

也就是二分這個時間，然后判斷該2-SAT是否有解。（因為這個間隔時間越小就也可能有合法解，反之越不可能，所以可以二分答案）
構圖的時候，如果兩個決策（比如說\(i_l,j_l\)）間隔小于二分的答案，我們就給\(i_l,j_r\)和\(i_r,j_l\)連有向邊。
然后跑tarjan判斷就行了，如果同一個飛機的兩個決策在一個強聯(lián)通分量里面，就沒有合法解了。
順便一提，劉汝佳書上寫的那個做法復雜度是假的qwq

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define MAXN 4010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,t,tot,cnt,top;
int head[MAXN],dfn[MAXN],low[MAXN],in[MAXN],st[MAXN],c[MAXN];
struct Edge{int nxt,to;}edge[MAXN*MAXN];
struct Node{int l,r;}node[MAXN];
inline void add(int from,int to){edge[  t].nxt=head[from],edge[t].to=to,head[from]=t;}
inline void tarjan(int x)
{
    dfn[x]=low[x]=  tot;
    in[x]=1;
    st[  top]=x;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    }
    if(dfn[x]==low[x])
    {
        int v;  cnt;
        do{v=st[top--],c[v]=cnt,in[v]=0;}while(x!=v);
    }
}
inline bool check(int x)
{
    memset(head,0,sizeof(head));
    t=tot=top=cnt=0;
    for(int i=1;i<=(n>>1);i  )
        for(int j=1;j<=(n>>1);j  )
        {
            if(i==j) continue;
            int a=abs(node[i].l-node[j].l);
            int b=abs(node[i].l-node[j].r);
            int c=abs(node[i].r-node[j].l);
            int d=abs(node[i].r-node[j].r);
            if(a<x) add(i*2-1,j*2);
            if(b<x) add(i*2-1,j*2-1);
            if(c<x) add(i*2,j*2);
            if(d<x) add(i*2,j*2-1);
        }
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(in,0,sizeof(in));
    for(int i=1;i<=n;i  )
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<n;i =2)
        if(c[i]==c[i 1])
            return false;
    return true;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i  ) scanf("%d%d",&node[i].l,&node[i].r);
        n<<=1;
        int l=0,r=INF,ans=0;
        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;
}

例題10 宇航員分組

有A，B，C三種任務要分配給n個宇航員，其中每個宇航員恰好要分配一個任務。設所有n個宇航員的平均年齡為x，只有年齡大于或等于x的宇航員才能分配任務A；只有年齡嚴格小于x的宇航員才能分配任務B，而任務C沒有限制。有m對宇航員相互討厭，因此不能分配到統(tǒng)一任務?，F(xiàn)在需要找出一個滿足上訴所有要求的任務分配方案。

3-SAT？？？不可能的。我們只要處理一下年齡，對于每個宇航員，照樣是2-SAT.
然后就......和上面那題一樣做就行了??？？
但是為什么會RE啊......搞不懂......先把代碼貼上，回來找鍋（咕咕咕）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,all,kkk,cnt,tot,top,t;
int head[MAXN],done[MAXN];
int dfn[MAXN],low[MAXN],in[MAXN],st[MAXN],c[MAXN];
char op[MAXN];
struct Node{int l,r,age;}node[MAXN];
struct Edge{int nxt,to;}edge[MAXN<<1];
struct Line{int u,v;}line[MAXN<<1];
inline void add(int from,int to){edge[  t].nxt=head[from],edge[t].to=to,head[from]=t;}
inline void tarjan(int x)
{
    low[x]=dfn[x]=  tot;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
        else if(in[v]) low[x]=min(low[x],dfn[v]);
    }
    if(low[x]==dfn[x])
    {
        int v;  cnt;
        do{v=st[top--];in[v]=0;c[v]=  cnt;}while(x!=v);
    }
}
inline bool check()
{
    memset(head,0,sizeof(head));
    memset(in,0,sizeof(in));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    top=tot=t=cnt=0;
    for(int i=1;i<=m;i  )
    {
        int u=line[i].u,v=line[i].v;
        if(node[u].age^node[v].age) 
        {
            add(node[u].r,node[v].l),printf("%d %d\n",node[u].r,node[v].l);
            add(node[v].r,node[u].l),printf("%d %d\n",node[v].r,node[u].l);
        }
        else
        {
            add(node[u].l,node[v].r),printf("%d %d\n",node[u].l,node[v].r);
            add(node[u].r,node[v].l),printf("%d %d\n",node[u].r,node[v].l);
            add(node[v].l,node[u].r),printf("%d %d\n",node[v].l,node[u].r);
            add(node[v].r,node[u].l),printf("%d %d\n",node[v].r,node[u].l);
        }
    }
    for(int i=1;i<=n;i  )
        if(!dfn[i])
            tarjan(i),cout<<i<<endl;
    for(int i=1;i<=n;i  )
        if(c[node[i].l]==c[node[i].r]&&c[node[i].l]!=0)
            return false;
    return true;
}
inline bool solve(int x,int c)
{
    done[x]=c,done[x^1]=3-c;
    printf("done[%d]=%d done[%d]=%d\n",x,done[x],x^1,done[x^1]);
    cout<<endl;
    for(int i=head[x];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(done[v]&&done[v]==c) return false; 
        else if(!done[v]) solve(v,c);
    }
    return true;
}
inline void print()
{
    cout<<"yes"<<endl;
    for(int i=1;i<=n;i  )
    {
        if(done[node[i].l]==1) printf("%c\n",op[node[i].l]);
        else if(done[node[i].l]==0&&done[node[i].r]==0) printf("%c\n",op[node[i].l]);
    }
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0&&m==0) break;
        memset(head,0,sizeof(head));
        top=tot=t=cnt=all=0;
        for(int i=1;i<=n;i  ) scanf("%d",&node[i].age),all =node[i].age;
        all/=n;
        for(int i=1;i<=n;i  )
        {
            if(node[i].age<all) node[i].age=0;
            else node[i].age=1;
        }
        for(int i=1;i<=n;i  ) scanf("%d%d",&line[i].u,&line[i].v);
        for(int i=1;i<=n;i  ) 
            if(node[i].age==0) 
                node[i].l=  kkk,op[kkk]='B',node[i].r=  kkk,op[kkk]='C';
            else 
                node[i].l=  kkk,op[kkk]='A',node[i].r=  kkk,op[kkk]='C';
        for(int i=1;i<=n;i  )
            printf("%c %c\n",op[node[i].l],op[node[i].r]);
        if(check()==false) {printf("No solution.\n");continue;}
        memset(done,0,sizeof(done));
        bool flag=true;
        for(int i=1;i<=n;i  )
            if(!done[i])
                if(solve(node[i].l,1))
                    flag=false;
        if(flag==true) {print();continue;}
        memset(done,0,sizeof(done));
        flag=true;
        for(int i=1;i<=n;i  )
            if(!done[i])
                solve(node[i].r,1);
        print();
    }
    return 0;
}

例題11 機場快線

機場快線分為經(jīng)濟線和商業(yè)線兩種，線路、速度和價錢都不同?，F(xiàn)在你有一張商業(yè)線的車票，可以坐一站商業(yè)線，而其他時候只能乘坐經(jīng)濟線。假設換成時間忽略不計，你的任務是找一條取機場最快的線路，然后輸出方案。（保證最優(yōu)解唯一）

因為商業(yè)線只能坐一站，而且數(shù)據(jù)范圍在1000以內(nèi)，所以我們可以枚舉坐的是哪一站。
假設我們用商業(yè)線車票從車站a坐到b，則從起點到a，從b到終點這兩部分的路線對于只存在經(jīng)濟線的圖中一定是最短路。所以我們只需要從起點、終點開始做兩次最短路，記錄下從起點到每個點x的最短時間\(f(x)\)和它到終點的最短時間\(g(x)\)，那么總時間就是\(f(a) time(a,b) g(b)\)。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int mod = 1000000000   7;
const int INF = 1000000000;
const int maxn = 500   10;
int T,n,m,S,d1[maxn], p1[maxn], d2[maxn], p2[maxn], vis[maxn], ok, dist;
struct node {
    int u, val;
    node(int u=0, int val=0):u(u), val(val) {}
    bool operator < (const node& rhs) const {
        return val > rhs.val;
    }
};
void print(int root, int p[], int id, int S) {
    vector<int> ans;
    while(root != S) {
        ans.push_back(root);
        root = p[root];
    }
    ans.push_back(root);
    int len = ans.size();
 
    if(id == 1) for(int i=len-1;i>=0;i--) {
        if(i != len-1) printf(" ");
        printf("%d",ans[i]);
    }
    else for(int i=0;i<len;i  ) {
        if(i != 0) printf(" ");
        printf("%d",ans[i]);
    }
}
vector<node> g[maxn];
void BFS(int haha, int d[], int p[]) {
    priority_queue<node> q;
    q.push(node(haha, 0));
    for(int i=1;i<=n;i  ) {
        d[i] = INF;
    }
    d[haha] = 0;
    memset(vis, false, sizeof(vis));
    while(!q.empty()) {
        node u = q.top(); q.pop();
        if(vis[u.u]) continue;
        vis[u.u] = true;
        int len = g[u.u].size();
        for(int i=0;i<len;i  ) {
            node v = g[u.u][i];
            if(d[v.u] > d[u.u]   v.val) {
                d[v.u] = d[u.u]   v.val;
                p[v.u] = u.u;
                q.push(node(v.u, d[v.u]));
            }
        }
    }
}
int a,b,c,kase=0;
int main() {
    #ifndef ONLINE_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(~scanf("%d%d%d",&n,&S,&T)) {
        scanf("%d",&m);
        for(int i=1;i<=n;i  ) g[i].clear();
        while(m--) {
            scanf("%d%d%d",&a,&b,&c);
            g[a].push_back(node(b, c));
            g[b].push_back(node(a, c));
        }
        scanf("%d",&m);
        ok = -1;
        BFS(S, d1, p1);
        BFS(T, d2, p2);
        int s = -1,t = -1,ans = d1[T], res = 0;
        for(int i=0;i<m;i  ) {
            scanf("%d%d%d",&a,&b,&c);
            if(cur < ans) {
                ans = cur;
                s = b; t = a;
            }
        }
        if(kase) printf("\n");
        else   kase;
        if(s > 0) {
            print(s, p1, 1, S); printf(" ");
            print(t, p2, 2, T); printf("\n");
            printf("%d\n",s);
        }
        else {
            print(T, p1, 1, S); printf("\n");
            printf("Ticket Not Used\n");
        }
        printf("%d\n",ans);
    }
    return 0;
}

書上還提到了dij算法的路徑統(tǒng)計，在這里就簡單說一下吧
枚舉兩點之間的所有最短路：先求出所有點到目標點的最短路長度\(d[i]\),然后從起點開始出發(fā)，只沿著\(d[i]=d[j] dist(i,j)\)的邊走。
兩點之間的最短路計數(shù)：令\(f[i]\)表示從i到目標點的最短路的條數(shù)，則\(f[i]=\sum f[j] | d[i]=d[j] dist(i,j)\)（這里書上寫錯了）

例題12 林中漫步

對于一張圖，只沿著滿足如下條件的道路（A,B）走：存在一條從B出發(fā)回家的路徑，比所有從A出發(fā)回家的路徑都短。問不同的回家路徑條數(shù)。

先跑完以家為源點的最短路，然后如果一個點a的最短路比b的小，那么連邊，這就是一個DAG了，然后再DP計個數(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_JUDGE
    freopen("ce.in","r",stdin);
    #endif
    while(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]\)時除了更新\(d[j]\)之外還要設置\(p[j]=i\)。這樣，所有點就形成了一棵樹。
要從起點出發(fā)沿著最短路走到其他任意點，只需要順著樹上的邊走即可。