社区讨论

萌新刚学OI,求助大佬

P2153[SDOI2009] 晨跑参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi862vja
此快照首次捕获于
2025/11/21 09:13
4 个月前
此快照最后确认于
2025/11/21 09:13
4 个月前
查看原帖
估计是建图写挂了,MCMF应该没什么问题,请各位大佬帮忙看看
码风可能有点奇怪,大家将就着看吧QAQ
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,c,d,n,m,Sum,Cnt,Maxflow,Min,Start,End,Head[5010],Dist[5010],From[5010],Pre[5010],To[100010],Next[100010],Val[100010],Cost[100010];
ll Q[100010],Front,Back;
template <typename T>
int Read(T &x){
    x=0;
    int f=1;
    char c=getchar();
    while(c!='-'&&!isdigit(c)){
        c=getchar();
    }
    while(!isdigit(c)){
        if(c=='-'){
            f=-f;
        }
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    if(c=='\n'){
        return 1;
    }
    else{
        return 0;
    }
}
inline void Write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9){
        Write(x/10);
    }
    putchar(x%10+'0');
}
inline void Clear(){
    Front=0;
    Back=0;
    memset(From,-1,sizeof(From));
    memset(Pre,-1,sizeof(Pre));
    memset(Dist,0x7f,sizeof(Dist));
}
inline void Add(ll a,ll b,ll c,ll d){
    To[++Cnt]=b;
    Next[Cnt]=Head[a];
    Head[a]=Cnt;
    Val[Cnt]=c;
    Cost[Cnt]=d;
    To[++Cnt]=a;
    Next[Cnt]=Head[b];
    Head[b]=Cnt;
    Val[Cnt]=0;
    Cost[Cnt]=-d;
}
void Init(){
    Cnt=1;
    Maxflow=0;
    Sum=0;   
    Read(m);
    Read(n);
    Start=n*m+n+1;
    End=n*m+n+2;
    for(int i=1;i<=n;i++){
    	Add(Start,m*n+i,1,0);
    }
    for(int i=1;i<=n*m;i++){
        Add(i,End,1,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            Read(c);
            for(int k=1;k<=n;k++){
                Add(m*n+i,(j-1)*m+k,1,k*c);
            }
        }
    }
}
bool Spfa(){
    int x,y;
    Clear();
    Q[++Back]=Start;
    Dist[Start]=0;
    while(Front<=Back){
        x=Q[Front];
        Front++;
        for(int i=Head[x];i;i=Next[i]){
            y=To[i];
            if(Dist[y]>Dist[x]+Cost[i]&&Val[i]){
                Dist[y]=Dist[x]+Cost[i];
                From[y]=x;
                Pre[y]=i;
                Q[++Back]=y;
            }
        }
    }
    return ~From[End];
}
void Costflow(){
    while(Spfa()){
        Min=0x7f7f7f7f;
        for(int i=End;i!=Start;i=From[i]){
            Min=min(Min,Val[Pre[i]]);
        }
        Maxflow+=Min;
        Sum+=Dist[End]*Min;
        for(int i=End;i!=Start;i=From[i]){
            Val[Pre[i]]-=Min;
            Val[Pre[i]^1]+=Min;
        }
    }
}
void Output(){
    printf("%.2lf\n",1.0*Sum/n);
}
int main(){
    Init();
    Costflow();
    Output(); 
}

回复

2 条回复,欢迎继续交流。

正在加载回复...