bzoj2285:[Sdoi2011]保密(分数规划+spfa+最小割)

题解

  我也不知道这破题为什么我会调这么久…
  题意挺绕的,理解了好久,感觉就是强行把两道水题拼起来而已,luogu上居然还能评个黑色,惊了…
  首先显然分数规划,求出n1n_1内每个点的最小危险值,然后就是要选一些点使危险值之和最小。
  剩下的就是最小点权覆盖了…SS连奇数点,偶数点连TT,容量都是点上的最小危险值,对于一个空腔的出入口连边容量infinf即可。
  也就是说这个破题就是个码农题…锻炼调代码能力而已…

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=500010;
const double inf=1e100;
const double eps=1e-5;
struct edge{int too, t, s, pre;}e[maxn];
struct poi{int too; double cf; int pre;}e2[maxn];
int n, m, n1, m1, x, y, z, g, tot, tot2, s, t;
int fir[maxn], sec[maxn], last[maxn], cur[maxn], last2[maxn], h[maxn];
double ans, dist[maxn], val[maxn];
bool v[maxn];
 
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;   
} 
 
inline void add(int x, int y, int z, int l){e[++tot]=(edge){y, z, l, last[x]}; last[x]=tot;}
 
inline void add2(int x, int y, double z){e2[++tot2]=(poi){y, z, last2[x]}; last2[x]=tot2;}
 
inline void ins(int x, int y, double z){add2(x, y, z); add2(y, x, 0);}
 
inline bool spfa(int s, int t, double p)
{
    for(int i=1;i<=n;i++) dist[i]=inf, v[i]=0;
    dist[s]=0; v[s]=1; int front=0, rear=1; h[1]=s;
    while(front!=rear)
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last[now], too;i;i=e[i].pre)
        if(dist[too=e[i].too]>dist[now]+e[i].t-p*e[i].s+eps)
        {
            dist[too]=dist[now]+e[i].t-p*e[i].s;
            if(too==t && dist[t]<-eps) return 1;
            if(!v[too])
            {
                v[too]=1; h[++rear]=too;
                if(rear==maxn-1) rear=-1;
            }
        }
        v[now]=0;
    }
    return dist[t]<-eps;
}
 
inline bool bfs(int s, int t)
{
    for(int i=0;i<=t;i++) dist[i]=-1, v[i]=0;
    v[s]=1; dist[s]=0; int front=0, rear=1; h[1]=s;
    while(front!=rear)  
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last2[now], too;i;i=e2[i].pre)
        if(!v[too=e2[i].too] && e2[i].cf>eps)
        {
            dist[too]=dist[now]+1;
            v[too]=1; h[++rear]=too;
            if(too==t) return 1;    
            if(rear==maxn-1) rear=-1;
        } 
    }
    return 0;
}
 
inline double dfs(int x, double flow)
{
    if(x==t || flow<eps) return flow;
    double f=0;
    for(int &i=cur[x], too;i;i=e2[i].pre)
    if(dist[too=e2[i].too]==dist[x]+1 && e2[i].cf>eps)
    {
        double tmp=dfs(too, min(flow-f, e2[i].cf));
        e2[i].cf-=tmp; e2[i^1].cf+=tmp; f+=tmp;
        if(f==flow) break; 
    }
    return f;
}
 
inline void dinic(int s, int t)
{
    while(bfs(s, t))
    {
        memcpy(cur, last2, sizeof(last2));
        ans+=dfs(s, inf);       
    }
}
 
int main()
{
    read(n); read(m); int sum=0; tot2=1;
    for(int i=1;i<=m;i++)
    read(x), read(y), read(z), read(g), add(x, y, z, g), sum+=z;
    read(m1); read(n1); s=0; t=n1+1;
    for(int i=1;i<=n1;i++)
    {
        double l=0, r=sum;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            if(spfa(n, i, mid)) r=mid;
            else l=mid;
        }
        val[i]=l;
    }
    spfa(n, 0, 0);
    for(int i=1;i<=m1;i++) 
    {
        read(fir[i]); read(sec[i]);
        if(fabs(dist[fir[i]]-inf)<eps && fabs(dist[fir[i]]-inf)<eps) return puts("-1"), 0;
        add2(fir[i], sec[i], inf); add2(sec[i], fir[i], inf);
    }
    for(int i=1;i<=n1;i++) 
    if(i&1) ins(s, i, val[i]); else ins(i, t, val[i]);
    dinic(s, t);
    printf("%.1lf\n", ans);
}