我可能写了假的费用流

回复帖子

@Lapis 2018-04-06 19:29 回复

个人认为这题应该是最大费用最大流来着,写了之后连样例都过不去

一气之下改成了最小费用最大流,不仅过了样例还A了?

关键是我A后看题解齐刷刷的一片最大费用最大流,随便交了题解里的一个代码上去也A了……(自己先A再试别人的代码应该不算作弊吧orz)

我现在感到很害怕QWQ

@Lapis 2018-04-06 19:32 回复

嗯贴一下那个交都不敢交的最大费用最大流代码

#include <bits/stdc++.h>
using namespace std;
const int N=110;
const double eps=0.0000001;
int head[N<<1],u[N<<8],v[N<<8],nxt[N<<8],f[N<<8],a[N][N],b[N][N],cnt=1,s,t,vis[N<<1],fa[N<<1],path[N<<1];
double w[N<<8],dis[N<<1];
inline void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
inline void add(int uu,int vv){
    u[++cnt]=uu,v[cnt]=vv,f[cnt]=1,nxt[cnt]=head[uu],head[uu]=cnt;
    u[++cnt]=vv,v[cnt]=uu,f[cnt]=0,nxt[cnt]=head[vv],head[vv]=cnt;
}
inline bool spfa(){
    memset(dis,0x43,sizeof(dis));
    memset(vis,0,sizeof(vis));
    memset(fa,-1,sizeof(fa));
    queue<int>q;
    vis[s]=1,dis[s]=0,q.push(s);
    while(!q.empty()){
        register int x=q.front();
        q.pop(),vis[x]=0;
        for(register int i=head[x];i;i=nxt[i]){
            register int to=v[i];
            if(dis[to]>dis[x]+w[i] && f[i]){
                dis[to]=dis[x]+w[i],fa[to]=x,path[to]=i;
                if(!vis[to]) vis[to]=1,q.push(to);
            }
        }
    }
    return ~fa[t];
}
int main(){
    register int n,i,j,be;
    register double l=0,r=0,cost=0;
    read(n);
    memset(w,0,sizeof(w));
    s=0,t=(n<<1)+1;
    for(i=1;i<=n;i++){
        add(s,i),add(i+n,t);
        for(j=1;j<=n;j++)
            read(a[i][j]),r=(double)r+a[i][j];      
    }
    be=cnt+1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            read(b[i][j]),add(i,j+n);
     while(l+eps<r){
        cost=0;
        double mid=(l+r)/2;
        for(i=2;i<be;i+=2) f[i]=1,f[i^1]=0;
        for(i=be;i<=cnt;i+=2)
            w[i]=(double)mid*b[u[i]][v[i]-n]-a[u[i]][v[i]-n],f[i]=1,w[i^1]=-w[i],f[i^1]=0;
        while(spfa()){
            cost+=dis[t];
            for(i=t;i!=s;i=fa[i]) f[path[i]]--,f[path[i]^1]++;
        }
        if(cost>=0) r=mid;
        else l=mid;
     }
     printf("%.6f",r); 
} 
@Lapis 2018-04-08 21:39 回复

好了对不起我推式子推错了,真是太丢脸了,我退群吧(捂脸逃~)