MLE 40 pts 求助
查看原帖
MLE 40 pts 求助
581928
jasonliujiahua楼主2023/12/10 20:22
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int N=2010,maxn=1e5;
int m,n,cnt=1,s,t,ans,dis[N],rad[N];
bool in[N];
struct edge
{
    int u,v,w,c,nxt;
}e[maxn<<1];
int head[N];
queue<int> q;
inline void add(int x,int y,int z,int c)
{
    e[++cnt]=(edge){x,y,z,c,head[x]};
    head[x]=cnt;
    e[++cnt]=(edge){y,x,0,-c,head[y]};
    head[y]=cnt;
}
inline int id(int x,int y)
{
    return n+x*n+y;
}
void init()
{
    cin>>m>>n;
    s=id(m,n)+1,t=s+1;
    for(int i=1;i<=n;i++) add(s,i,1,0);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) 
            add(id(i,j),t,1,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            for(int k=1;k<=n;k++)
            {
                add(i,id(j,k),1,(n-k+1)*x);
            }
        }
    }
}
inline bool spfa()
{
    memset(dis,0x3f,sizeof(dis));
    memset(in,0,sizeof(in));
    q.push(s);
    dis[s]=0;
    in[s]=1;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        in[u]=0;
        rad[u]=head[u];
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(dis[v]<=dis[u]+e[i].c || !e[i].w) continue;
            dis[v]=dis[u]+e[i].c;
            if(!in[v])
            {
                in[v]=1;
                q.push(v);
            }
        }
    }
    return dis[t]!=dis[0];
}
int dfs(int u,int fl)
{
    if(u==t) 
    {
        ans+=dis[t]*fl;
        return fl;
    }
    int rest=fl;
    for(int i=rad[u];i;i=e[i].nxt)
    {
        rad[u]=i;
        int v=e[i].v,w=e[i].w;
        if(dis[v]!=dis[u]+e[i].c || !w) continue;
        int tmp=dfs(v,min(rest,w));
        e[i].w-=tmp;
        e[i^1].w+=tmp;
        rest-=tmp;
        if(rest==0) break;
    }
    return fl-rest;
}
void dinic()
{
    while(spfa()) dfs(s,1e9);
    printf("%.2lf",(double)ans/n);
}
signed main()
{
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    init();
    dinic();
    return 0;
}
2023/12/10 20:22
加载中...