求助,提交之后出现一些奇怪的错误
查看原帖
求助,提交之后出现一些奇怪的错误
401840
StarsWhisper楼主2021/4/16 21:43

在本地是可以跑对至少一部分数据的,(测试点1就是样例,可以跑对),但是提交之后莫名其妙显示我的第一行第一列是“-”,而不是5,没搞明白

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <cstring>
#include <vector>
#include <cmath>
#include <set>
typedef long long int LL;
const int N = 105,INF = 0x7fffffff;
int mp[N][N],lx[N],ly[N],visx[N],visy[N],link[N];
int n,tmp,v;
bool dfs(int x)
{
    visx[x] = 1;
    for(int i=1; i<=n; i++){
        if(!visy[i] && lx[x]+ly[i]==mp[x][i]){
            visy[i] = 1;
            if(!link[i] || dfs(link[i])){
                link[i] = x;
                return true;
            }
        }
    }
    return false;
}
int one()
{
    int ans;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        lx[i] = std::max(lx[i],mp[i][j]);
    }
    for(int i=1; i<=n; i++){
        while(true){
            memset(visx,0,sizeof(visx));
            memset(visy,0,sizeof(visy));
            tmp = INF;
            if(dfs(i)) break;
            for(int i=1; i<=n; i++){
                if(visx[i]){
                    for(int j=1; j<=n; j++){
                        if(!visy[j]){
                            tmp = std::min(tmp,lx[i]+ly[j]-mp[i][j]);
                        }
                    }
                }
            }
            for(int j=1; j<=n; j++){
                if(visx[j]) lx[j] -= tmp;
                if(visy[j]) ly[j] += tmp;
            }
        }
    }
    for(int i=1; i<=n; i++){
        ans += ly[i] + lx[link[i]];
    }
    return ans;
}
int main()
{
    //freopen("D:\\EdgeDownloadPlace\\P4014_1.in","r",stdin);
    scanf("%d",&n);
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        scanf("%d",&v);
        mp[i][j] = -v;
    }
    for(int i=0; i<N; i++) lx[i] = -INF;
    printf("%d\n",-one());
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++){
        mp[i][j] = -mp[i][j];
    }
    memset(lx,0,sizeof(lx));
    memset(ly,0,sizeof(ly));
    memset(link,0,sizeof(link));
    printf("%d\n",one());
    return 0;
}

2021/4/16 21:43
加载中...