[FZOJ190]網絡流+二分答案

FZOJ190

題目描述

• 神仙題，自閉場不要在意。了解了算法的思路，來寫一下部落格。（也就當是練一下闆子233）
• 做這道題大概是這樣一個思路過程：
  • 是在1~n的所有路徑上，選擇不超過k個點，點的權值變成1，使得最短路最大，求最大值。
  • 一般情況下，使最小值最大或者使最大值最小這種問題都是先二分答案。
  • 我們二分一個mid作為答案，那麼從1到n一共走了mid步。考慮怎麼判斷是否有可行解。
  • 首先應該考慮的是如何把點權轉化為邊的關系，然後想到拆點。從x0到x1連一條權值為1的邊，代表直接經過了x這個點。拆點一般什麼時候用啊？網絡流（不要問我什麼神仙想法，我也不知道啊）。是以應該建分層圖跑最小割判斷是否有可行解。
  • 為了使每個點的權值隻能貢獻一次，我們隻把目前層的x0與下一層的x1連一條容量為inf的邊。
  • 對于一條邊x，y，把每個目前層的x1向下一層的y0連一條容量為inf的邊。當然，每一層的n0也要向下一層的n0連一條容量inf的邊。
  • 求第1層的s1到第mid-1層的n0的最小割。最小割意味着什麼？畫一下圖，它代表的含義就是使用最少的點，讓s1無法到達第mid-1層的n0（無法到達mid-1的n0代表着它一定到達了mid-1層之後的分層圖，答案>=mid，符合條件）。
  • 哎，這題太神仙了。

Coding

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10;
const int inf=1e6;
struct node{int x,y;}e[N];long long maxflow,flow;
int n,m,k,s,t,tot,ver[N*50],Next[N*50],lin[N*50],edge[N*50],d[N*50];
int cal(int i,int j,int temp){return (i-1)*2*n+temp*n+j;}
void add(int x,int y,int z){
    ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z;
    ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0;
}
bool bfs(){
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(s);d[s]=1;
    while(q.size()){
        int x=q.front();q.pop();
        for(int i=lin[x];i;i=Next[i]){
            if(edge[i]){
                int y=ver[i];
                if(!d[y]){
                    d[y]=d[x]+1;
                    q.push(y);
                    if(y==t) return 1;
                }
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int rest=flow,num;
    for(int i=lin[x];i&&rest;i=Next[i]){
        int y=ver[i];
        if(edge[i]&&d[y]==d[x]+1){
            num=dinic(y,min(edge[i],rest));
            if(!num) d[y]=0;
            rest-=num;edge[i]-=num;edge[i^1]+=num;
            if(!rest) return flow-rest;
        }
    }
    return flow-rest;
}
bool check(int mid){
    memset(lin,0,sizeof(lin));
    memset(Next,0,sizeof(Next));
    tot=1;
    for(int i=1;i<=mid+1;++i){
        for(int j=2;j<n;++j) 
            add(cal(i,j,0),cal(i,j,1),1);
        if(i!=mid+1){
            for(int j=2;j<n;++j) 
                add(cal(i,j,0),cal(i+1,j,1),inf);
            add(cal(i,n,0),cal(i+1,n,0),inf);
            for(int j=1;j<=m;++j){
                add(cal(i,e[j].x,1),cal(i+1,e[j].y,0),inf);
                add(cal(i,e[j].y,1),cal(i+1,e[j].x,0),inf);
            }
        }
    }maxflow=0;
    s=cal(1,1,1);t=cal(mid+1,n,0);
    while(bfs()){
        while(flow=dinic(s,inf)) 
            maxflow+=flow;
        if(maxflow>k) return 0;
    }
    return maxflow<=k;
}
int main(){
    freopen("min.in","r",stdin);
    freopen("min.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&e[i].x,&e[i].y);
        e[i].x++,e[i].y++;
    }
    int l=0,r=2*n;
    while(l+1<r){
        int mid=l+r>>1;
        if(check(mid)) l=mid;
        else r=mid;
    }
    if(check(l)) printf("%d\n",r);
    else printf("%d\n",l);
    return 0;
}