CF267C

2016.02.18 20:22 Thu | 22次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给出一个网络,源点1汇点n,m条边,每条边可以正着流或反着流,流量有一个上界。求一个网络流满足流量最大的同时,对于任意一对点(x,y),满足x到y的任意一条路径上的流量之和都相等,可以有重边。
n<=100,m<=5000。

题解

考虑每个点的值,令f[u]表示从1到u的某条路径的流量和。则我们可以列出n个方程,一条边(u,v)的流量就是f[v]-f[u],用流量平衡可以解出f[i],然后考虑w[i]的限制。不妨令f[1]=0,f[n]=1,这样f[i]都在[0,1]中,我们取最小的
(w[i]/fabs(f[v[i]]-f[u[i]])),然后每个点的f值都乘以这个值就行了。
求最大流就把所有从1号点流出的流量算出来就可以了。

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 105
#define M 5005
#define eps 1e-9
char getc()
{   
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D,flag;
    while(!isdigit(ch=getc())&&ch!='-');
    if(ch=='-') ch=getc(),flag=1;else flag=0;
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return flag?D:-D;
}
int n,m,u[M],v[M];
double w[M],tmp=1e9,ans;
double f[N],a[N][N];
int gauss(int n,int m)
{
    static int sure[N],i,j,k,id;
    for(id=1,i=1;i<=m;i++,id++)
    {
        for(j=id;fabs(a[j][i])<eps&&j<=n;j++);
        if(j>n){id--;continue;}sure[id]=i;
        if(j!=id) for(k=i;k<=m+1;k++) swap(a[id][k],a[j][k]);
        for(j=id+1;j<=n;j++) if(fabs(a[j][i])>eps) 
        {
            double tmp=a[j][i]/a[id][i];
            for(k=i;k<=m+1;k++) a[j][k]-=a[id][k]*tmp;
        }
    }
    for(i=id;i<=n;i++) if(a[i][m+1]) return -1;
    if(id<=n) return 1;
    for(i=id-1;i;i--)
    {
        for(int j=i+1;j<id;j++) a[i][m+1]-=a[i][sure[j]]*f[sure[j]];
        a[i][m+1]/=a[i][sure[i]];
    }
    return 0;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lf",&u[i],&v[i],&w[i]);
        a[u[i]][u[i]]++;a[u[i]][v[i]]--;
        a[v[i]][v[i]]++;a[v[i]][u[i]]--;
    }
    memset(a[1],0,sizeof(a[1]));a[1][1]=1;
    memset(a[n],0,sizeof(a[n]));a[n][n]=1;
    f[n]=a[n][n+1]=1;
    gauss(n,n);
    for(int i=1;i<=m;i++) 
    {
        tmp=min(tmp,w[i]/fabs(f[u[i]]-f[v[i]]));
        if(u[i]==1) ans+=f[v[i]]-f[u[i]];
        if(v[i]==1) ans+=f[u[i]]-f[v[i]];
    }
    printf("%lf\n",ans*tmp);
    for(int i=1;i<=m;i++) printf("%lf\n",(f[v[i]]-f[u[i]])*tmp); 
}