QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388579#6113. Window ArrangementMladenP#TL 1ms4372kbC++142.7kb2024-04-13 17:07:322024-04-13 17:07:33

Judging History

你现在查看的是最新测评结果

  • [2024-04-13 17:07:33]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:4372kb
  • [2024-04-13 17:07:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define maxn 52
#define maxt 20000
int n,m;
int p[maxn][maxn];
int w[maxn][maxn];
int t;
struct eg{
    int v;
    int iv;
    int ca;
    int co;
};
vector<eg> g[maxt];
void add_edge(int u,int v,int ca,int co) {
    g[u].push_back({v,g[v].size(),ca,co});
    g[v].push_back({u,g[u].size()-1,0,-co});
}
long long inf=1e18;
long long lvl[maxt];
pair<int,int> par[maxn];
void init() {
    for(int i=0;i<=t;i++) {
        lvl[i]=inf;
    }
    lvl[0]=0;
}
void bf() {
    vector<int> q;
    q.push_back(0);
    //cout<<"in"<<endl;
    for(int it=0;it<q.size();it++) {
        int u=q[it];
        for(int i=0;i<g[u].size();i++) {
            int v=g[u][i].v;
            int j=g[u][i].iv;
            if(g[u][i].ca && lvl[u]+g[u][i].co<lvl[v]) {
                lvl[v]=lvl[u]+g[u][i].co;
                par[v]={u,i};
                q.push_back(v);
            }
        }
    }
    //cout<<"out"<<endl;
}
long long mcmf() {
    int r=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            r+=w[i][j];
        }
    }
    init();
    bf();
    long long ret=0;
    while(lvl[t]!=inf) {
        int v=t;
        while(v!=0) {
            int u=par[v].first;
            int i=par[v].second;
            int j=g[u][i].iv;
            ret+=g[u][i].co;
            g[u][i].ca-=1;
            g[v][j].ca+=1;
            v=u;
        }
        init();
        bf();
    }
    return ret;
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&p[i][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&w[i][j]);
            add_edge(0,(i-1)*m+j,w[i][j],0);
            add_edge((i-1)*m+j,n*m+(j-1)*(n+1)+i,1,0);
            add_edge((i-1)*m+j,n*m+(j-1)*(n+1)+i+1,1,0);
            add_edge((i-1)*m+j,n*m+(n+1)*m+(i-1)*(m+1)+j,1,0);
            add_edge((i-1)*m+j,n*m+(n+1)*m+(i-1)*(m+1)+j+1,1,0);
        }
    }
    t=n*m+(n+1)*m+(m+1)*n+1;
    for(int j=1;j<=m;j++) {
        add_edge(n*m+(j-1)*(n+1)+1,t,1,0);
        add_edge(n*m+(j-1)*(n+1)+1,t,1,0);
        for(int i=1;i<=n;i++) {
            add_edge(n*m+(j-1)*(n+1)+i+1,t,1,0);
            add_edge(n*m+(j-1)*(n+1)+i+1,t,1,p[i][j]*p[i+1][j]);
        }
    }
    for(int i=1;i<=n;i++) {
        add_edge(n*m+(n+1)*m+(i-1)*(m+1)+1,t,1,0);
        add_edge(n*m+(n+1)*m+(i-1)*(m+1)+1,t,1,0);
        for(int j=1;j<=m;j++) {
            add_edge(n*m+(n+1)*m+(i-1)*(m+1)+j+1,t,1,0);
            add_edge(n*m+(n+1)*m+(i-1)*(m+1)+j+1,t,1,p[i][j]*p[i][j+1]);
        }
    }
    printf("%lld",mcmf());
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4300kb

input:

4 3
1 7 10
7 2 8
7 9 10
4 6 4
3 3 3
3 2 4
4 3 4
2 2 3

output:

178

result:

ok 1 number(s): "178"

Test #2:

score: 0
Accepted
time: 1ms
memory: 4372kb

input:

4 3
2 2 9
9 8 4
8 4 5
7 5 2
0 1 0
1 0 1
0 0 1
0 1 0

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Time Limit Exceeded

input:

20 20
755 344 600 54 516 407 657 429 565 185 90 323 449 464 872 138 404 500 196 111
666 191 824 98 505 538 949 801 266 861 984 957 396 851 496 147 225 451 874 380
536 200 581 397 305 514 351 416 228 763 566 442 618 131 527 651 954 757 226 129
286 608 819 477 891 22 19 747 565 704 198 703 736 8 835 1...

output:


result: