QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #67730 | #4786. Balance | A_zjzj | WA | 3ms | 3404kb | C++14 | 1.1kb | 2022-12-11 16:08:12 | 2022-12-11 16:08:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;using ll=long long;const int N=55,V=N*2,E=N*N*2,INF=1e9;
int n,s,t,kk=1,a[N][N],dis[V],pre[V],mn[V],head[V];struct edges{int to,c,w,nex;}edge[E];
void add(int u,int v,int c,int w){
edge[++kk]={v,c,w,head[u]};head[u]=kk;
edge[++kk]={u,0,-w,head[v]};head[v]=kk;
}
bool bfs(){
queue<int>q;q.push(s);memset(dis,-0x3f,sizeof dis);dis[s]=0;mn[s]=INF;for(int u;!q.empty();q.pop()){
u=q.front();for(int i=head[u],v;v=edge[i].to,i;i=edge[i].nex)if(edge[i].c&&dis[v]<dis[u]+edge[i].w)
pre[v]=i,dis[v]=dis[u]+edge[i].w,mn[v]=min(mn[u],edge[i].c),q.push(v);
}return dis[t]>-INF;
}
int EK(){
int sum=0;for(;bfs();){
for(int u=t;u^s;u=edge[pre[u]^1].to){
edge[pre[u]].c-=mn[t];edge[pre[u]^1].c+=mn[t];
sum+=edge[pre[u]].w*mn[t];
}
}return sum;
}
int main(){
cin>>n;s=0;t=n+n+1;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j],add(i,j+n,1,a[i][j]);
for(int i=1;i<=n;i++)add(s,i,1,0),add(i+n,t,1,0);
cout<<EK()*n<<endl;
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<1<<"\n "[j<n];
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3356kb
input:
4 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
output:
16 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
result:
ok correct plan, good job!
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3404kb
input:
24 20594 15420 1258 6283 18795 7007 20323 16605 27476 270 2082 5286 32911 30847 17237 14187 9258 26749 27575 8042 2690 25493 23540 30506 15252 21600 26878 32384 22641 12550 29190 28725 33837 7235 6316 1318 10773 4177 6535 33628 31431 19567 25294 22712 18861 16725 25214 12950 29777 22466 16743 2033 3...
output:
18759816 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
wrong answer condition B[1][1] >= A[1][1] failed