QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #339030 | #7737. Extending Distance | WhangZjian | WA | 1ms | 8164kb | C++20 | 3.6kb | 2024-02-26 16:53:40 | 2024-02-26 16:53:44 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define id(x,y) ((x-1)*(m-1)+y)
#define rx(x) ((x-1)/(m-1)+1)
#define ry(x) ((x-1)%(m-1)+1)
using namespace std;
const int N=521,inf=0x3f3f3f3f3f3f3f3f;
struct edge{
int y,nxt,v,w,i;
edge(int y1,int n1,int v1,int w1,int i1):y(y1),nxt(n1),v(v1),w(w1),i(i1){}
edge(){}
}e[N*N];
int st,ed,cnt,ver;
int d[N],vis[N];
int head[N],cur[N];
void add(int x,int y,int v,int w,int i){
e[++cnt]=edge(y,head[x],v,w,i);
head[x]=cnt;
}
void build(int x,int y,int v,int w){
add(x,y,v,w,cnt+2);
add(y,x,v,0,cnt);
add(y,x,v,w,cnt+2);
add(x,y,v,0,cnt);
}
int dinic(int x,int flow){
if(x==ed||!flow) return flow;
int res=0;
vis[x]=1;
for(int i=cur[x];~i;i=e[i].nxt,cur[x]=i){
int y=e[i].y,v=e[i].v,w=e[i].w;
if(!w||(ver&&v)||vis[y]) continue;
if(ver&&d[y]!=d[x]+1) continue;
if(!ver&&d[y]!=d[x]+v) continue;
int tmp=dinic(y,min(flow,w));
e[i].w-=tmp,e[e[i].i].w+=tmp;
flow-=tmp,res+=tmp;
if(!flow) break;
}
vis[x]=0;
return res;
}
bool bfs(){
memset(d,0x3f,sizeof(d));
for(int i=st;i<=ed;i++) cur[i]=head[i];
queue<int> q;
d[st]=0,q.push(st);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];~i;i=e[i].nxt){
int y=e[i].y;
if(!e[i].w||e[i].v) continue;
if(d[x]+1<d[y]){
d[y]=d[x]+1;
q.push(y);
}
}
}
return d[ed]<inf;
}
bool spfa(){
memset(d,0x3f,sizeof(d));
memset(vis,0,sizeof(vis));
for(int i=st;i<=ed;i++) cur[i]=head[i];
queue<int> q;
d[st]=0,q.push(st);
while(!q.empty()){
int x=q.front();q.pop();
vis[x]=0;
for(int i=head[x];~i;i=e[i].nxt){
int y=e[i].y,v=e[i].v;
if(!e[i].w) continue;
if(d[x]+v<d[y]){
d[y]=d[x]+v;
if(!vis[y]) vis[y]=1,q.push(y);
}
}
}
return d[ed]<inf;
}
int n,m,k,ans;
int fl[2][N][N];
signed main(){
int T;
cin>>T;
while(T--){
memset(head,-1,sizeof(head));
cnt=ans=0;
cin>>n>>m>>k;
st=0,ed=(n-1)*(m-1)+1;
for(int i=1;i<=n;i++){
for(int j=1,w;j<m;j++){
scanf("%lld",&w);
fl[0][i][j]=w;
if(i==1) build(st,id(i,j),0,w),build(st,id(i,j),1,inf);
if(i==n) build(id(i-1,j),ed,0,w),build(id(i-1,j),ed,1,inf);
if(i!=1&&i!=n) build(id(i,j),id(i-1,j),0,w),build(id(i,j),id(i-1,j),1,inf);
}
}
for(int i=1;i<n;i++){
for(int j=1,w;j<=m;j++){
scanf("%lld",&w);
fl[1][i][j]=w;
if(j==1||j==m) continue;
build(id(i,j-1),id(i,j),0,w);
build(id(i,j-1),id(i,j),1,inf);
}
}
ver=1;
while(bfs()){
dinic(st,inf);
}
ver=0;
while(k>0&&spfa()){
memset(vis,0,sizeof(vis));
k-=dinic(st,k);
}
for(int i=head[ed];~i;i=e[i].nxt){
if(!e[i].v||e[i].i>i) continue;
int y=e[i].y,i1=rx(y),j1=ry(y),w=e[i].w;
fl[0][n][j1]+=w;
}
for(int i=head[st];~i;i=e[i].nxt){
if(!e[i].v||e[i].i>i) continue;
int y=e[i].y,i1=rx(y),j1=ry(y),w=e[i].w;
fl[0][1][j1]+=w;
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
int x=id(i,j);
for(int t=head[x];~t;t=e[t].nxt){
if(!e[t].v||!e[t].w||e[t].i>t) continue;
int y=e[t].y,i1=rx(y),j1=ry(y),w=e[t].w;
if(y==ed) fl[0][n][j]+=w;
else if(y==st) fl[0][1][j]+=w;
else if(i1==i-1) fl[0][i][j]+=w;
else if(i1==i+1) fl[0][i+1][j]+=w;
else if(j1==j-1) fl[1][i][j]+=w;
else if(j1==j+1) fl[1][i][j+1]+=w;
// ans+=w;
}
}
}
for(int i=1;i<=cnt;i++){
if(!e[i].v||e[i].i>i) continue;
ans+=e[i].w;
}
printf("%lld\n",ans);
for(int i=1;i<=n;i++){
for(int j=1;j<m;j++){
printf("%lld",fl[0][i][j]);
if(j!=m-1) printf(" ");
}
printf("\n");
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
printf("%lld",fl[1][i][j]);
if(j!=m) printf(" ");
}
printf("\n");
}
}
}
/*
2
3 4 6
2 1 15
7 1 9
13 3 2
3 6 1 2
5 2 15 3
3 3 3
1 1
2 2
3 3
1 1 1
2 2 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7936kb
input:
2 3 4 6 2 1 15 7 1 9 13 3 2 3 6 1 2 5 2 15 3 3 3 3 1 1 2 2 3 3 1 1 1 2 2 2
output:
9 2 1 15 8 1 9 13 3 4 3 6 6 2 5 3 15 3 4 1 4 2 3 3 3 1 1 1 2 2 2
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 8164kb
input:
125 4 4 48 33 9 39 38 74 3 18 44 9 20 91 19 76 95 17 16 61 88 50 49 68 18 33 84 4 4 14 54 69 42 47 90 28 2 73 59 1 20 90 43 22 74 19 27 67 46 43 42 21 78 80 4 4 93 12 67 38 13 85 39 74 68 77 71 80 64 92 97 53 46 66 6 30 20 66 70 71 24 4 4 34 43 86 55 49 34 73 78 77 90 99 49 5 55 4 63 47 80 24 15 3 8...
output:
87 33 38 39 38 74 3 18 44 48 20 91 19 76 95 36 16 61 88 50 49 68 18 33 84 14 54 69 42 47 90 28 2 73 59 1 20 104 43 22 74 19 27 67 46 43 42 21 78 80 166 12 80 118 59 86 65 74 68 77 71 80 64 92 97 53 46 66 6 30 20 66 70 71 24 34 43 86 55 49 38 73 78 77 90 99 49 28 55 6 63 47 80 24 20 3 85 12 6 31 45 4...
result:
wrong answer Jury has better answer than participant. (test case 9)