bzoj 2285 [Sdoi2011]保密（二分，spfa + 最大流）

Description

       现在，保密成为一个很重要也很困难的问题。如果没有做好，后果是严重的。比如，有个人没有自己去修电脑，又没有拆硬盘，后来的事大家都知道了。

       当然，对保密最需求的当然是军方，其次才是像那个人。为了应付现在天上飞来飞去的卫星，军事基地一般都会建造在地下。

       某K国的军事基地是这样子的：地面上两排大天井共n1个作为出入口，内部是许多除可以共享出入口外互不连通的空腔，每个空腔有且只有两个出入口，并且这两个出入口不会在同一排。为了方便起见，两排出入口分别编号为1,3,5…和2,4,6…并且最大的编号为n1。

       虽然上面扯了那么多关于保密的东西，但是其实解密也是一件很纠结的事情。但其实最简单直接暴力无脑的解密方法就是找个人去看看。。。

       我们有很牛X的特种部队，只需要派出一支特种部队到K国基地的某个出入口，那么和这个出入口直接相连的所有空腔都可以被探索，但也只有这些空腔可以被这支部队探索。现在有足够多的特种部队可以供你调遣，你必须使用他们调查完所有的K国基地内的空腔。

       当然，你的基地离K国基地不会太近，周边的地图将会给你，表示为n个检查点和m条连接这些点的道路，其中点1到点n1就是K国基地的出入口，点n是你的部队的出发点。对每条道路，有不同的通行时间t和安全系数s。因为情报部门只对单向的道路安全系数进行了评估，所以这些道路只允许单向通行，并且不会存在环。

       一支特种部队从你的基地出发，通过某条路径，到达某个K国基地出入口，此时这支部队的危险性表示为总时间和这条路径经过的所有道路的安全系数和的比值。整个行动的危险性表示为你派出的所有部队的危险性之和。你需要使这个值最小的情况下探索整个K国基地。

       快点完成这个任务，在K国的叫兽宣布你是K国人之前。

Input

       第一行2个正整数n，m (4 <= n <= 700, m <= 100000) 表示整个地区地图上的检查点和道路数。

       下面m行，每行4个正整数a, b, t, s(a, b <=n, 1 <= t, s <= 10)表示一条从a到b的道路需时为t，安全系数为s。

       接下来1行2个正整数m1和n1(m1 <= 40000, n1 < min{n, 161}), m1表示K国基地空腔的个数，n1表示K国基地出入口的个数。

       再接下来m1行，每行2个正整数u, v (u, v<=n1, u是奇数，v是偶数)，表示每个空腔的2个出入口。 

 

Output

 

       一行，最小的危险性，保留一位小数。或者输出”-1”（无引号）表示此任务不可能完成。

Sample Input

5 5

5 1 10 1

5 1 10 1

5 2 9 1

5 3 7 1

5 4 8 1

4 4

1 2

1 4

3 2

3 4

Sample Output

17.0

 

【思路】

       二分，spfa + 最大流

       首先求出从起点到所有出入口的危险性val，题目就是一个最小覆盖的问题，按照奇偶性将节点分作两组，奇数点由S向之连边val，偶数点向T连边val，跑个最大流就好了。

       问题是怎么求出危险性。假设答案是ans，如果存在

              (t1+t2+…tn)/(s1+s2+…sn)<=ans

       即

              t1-ans*s1+t2-ans*s2+…tn-ans*sn<=0

       则说明存在更小ans。二分ans，每次跑一遍spfa求出最短路即可。

【代码】

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std;

const int N = 805;
const double INF = 1e12;
const double eps = 1e-8;
struct Edge{
    int v; double t,s; 
    Edge(int v,double t,double s) :v(v),t(t),s(s) {}
};
struct Dedge {
    int u,v; double cap,flow; 
    Dedge(int u,int v,double cap,double flow) :u(u),v(v),cap(cap),flow(flow) {}
};

void read(int& x) {
    char c=getchar(); int f=1; x=0;
    while(!isdigit(c)) {if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    x*=f;
}

struct Dinic {
    vector<int> G[N];
    vector<Dedge> es;
    int n,m,s,t,d[N],cur[N],vis[N];
    void init(int n) {
        this->n=n;
        es.clear();
        for(int i=0;i<n;i++) G[i].clear();
    }
    void AddEdge(int u,int v,double w) {
        es.push_back(Dedge(u,v,w,0));
        es.push_back(Dedge(v,u,0,0));
        m=es.size();
        G[u].push_back(m-2),G[v].push_back(m-1);
    }
    bool bfs() {
        int q[N],head=0,tail=0;
        memset(vis,0,sizeof(vis));
        q[tail++]=s; vis[s]=1; d[s]=0;
        while(head!=tail) {
            int u=q[head++];
            for(int i=0;i<G[u].size();i++) {
                Dedge& e=es[G[u][i]];
                int v=e.v;
                if(!vis[v]&&e.cap>e.flow) {
                    vis[v]=1; d[v]=d[u]+1;
                    q[tail++]=v;
                }
            }
        }
        return vis[t];
     }
     double dfs(int u,double a) {
         if(u==t||fabs(a)<eps) return a;
         double flow=0,f;
         for(int& i=cur[u];i<G[u].size();i++) {
             Dedge& e=es[G[u][i]];
             int v=e.v;
             if(d[v]==d[u]+1 && (f=dfs(v,min(a,e.cap-e.flow)))>eps) {
                 e.flow+=f;
                 es[G[u][i]^1].flow-=f;
                 flow+=f; a-=f;
                 if(fabs(a)<eps) break;
             }
         }
         return flow;
     }
     double Maxflow(int s,int t) {
         this->s=s,this->t=t;
         double flow=0;
         while(bfs()) {
             memset(cur,0,sizeof(cur));
             flow+=dfs(s,INF);
         }
         return flow;
     }
} dc;

vector<Edge> g[N];
int n,m,m1,n1; double val[N];
int head,tail,q[1600],vis[N]; double dis[N];    //spfa µÄ que 

bool spfa(int s,int t,double p) {
    FOR(i,1,n) dis[i]=INF;
    memset(vis,0,sizeof(vis));
    head=tail=0; q[tail++]=s;
    vis[s]=1; dis[s]=0;
    while(head!=tail) {
        int u=q[head++]; vis[u]=0;
        for(int i=0;i<g[u].size();i++) {
            int v=g[u][i].v; 
            if(dis[v]>dis[u]+g[u][i].t-p*g[u][i].s) {
                dis[v]=dis[u]+g[u][i].t-p*g[u][i].s;
                if(v==t&&dis[v]<eps) return 1;
                if(!vis[v])
                    vis[v]=1 , q[tail++]=v;
            }
        }
    }
    return dis[t]<-eps;
}

int main() {
    //freopen("in.in","r",stdin);
    //freopen("out.out","w",stdout);
    read(n),read(m);
    int u,v,s,t;
    FOR(i,1,m) {
        read(u),read(v),read(t),read(s);
        g[u].push_back(Edge(v,(double)t,(double)s));
    }
    read(m1),read(n1);
    FOR(i,1,n1) {
        double L=0,R=100,M;
        while((double)R-L>1e-4) {
            M=(L+R)*0.5;
            if(spfa(n,i,M)) R=M; else L=M;
        }
        if(dis[i]==INF) val[i]=INF; else val[i]=(L+R)*0.5;
    }
    dc.init(n1+2);
    int S=0,T=n1+1;
    FOR(i,1,m1) {
        read(u),read(v);
        if(v&1) swap(u,v);
        if(val[u]==INF&&val[v]==INF) {
            puts("-1"); return 0;
        }
        dc.AddEdge(u,v,INF);
    }
    FOR(i,1,n1) {
        if(i&1) dc.AddEdge(S,i,val[i]);
        else dc.AddEdge(i,T,val[i]);
    }
    printf("%.1lf",dc.Maxflow(S,T));
    return 0;
}

ps：原来我大SD也有如此放（si）荡（xiang）不（wo）羁（chuo）的出题人

spfa的队列要开大一点！spfa的队列要开大一点！spfa的队列要开大一点！

难得一次不用STL，你就wa给我看<_<