求条1pts，玄关
- 板块P4003 无限之环
- 楼主System_Error_/se
- 当前回复3
- 已保存回复3
- 发布时间2024/7/17 00:07
- 上次更新2024/7/17 09:06:07
查看原帖
被骇客银狼阻止的越权访问保存失败
求条1pts，玄关
#include<bits/stdc++.h>
using namespace std;
const int N=2005,M=1e6+5;
int n,m,a[N][N],dx[]={-1,1,0,0},dy[]={0,0,-1,1},s,t;
int dis[M],inque[M],cnt=1,head[M],cur[M],cost=0,mx=0;
struct node {int to,nxt,w,c;}e[M<<1];
void add(int u,int v,int w,int c) {
e[++cnt]=(node){v,head[u],w,c};head[u]=cnt;
e[++cnt]=(node){u,head[v],0,-c};head[v]=cnt;
}
int turn(int x,int y,int z) {return 4*((x-1)*m+y)+z;}
int count(int x) {int sum=0;while(x) sum++,x=x&(x-1);return sum;}
bool spfa() {
queue<int> q;
q.push(s);
memset(dis,0x3f,sizeof(dis)),memset(inque,0,sizeof(inque));
dis[s]=0,inque[s]=1;
while(!q.empty()) {
int u=q.front();
q.pop();
inque[u]=0;
for(int i=head[u]; ~i; i=e[i].nxt) {
int v=e[i].to;
if(dis[u]+e[i].c<dis[v]&&e[i].w) {
dis[v]=dis[u]+e[i].c;
if(!inque[v]) q.push(v),inque[v]=1;
}
}
}
return dis[t]!=0x3f3f3f3f;
}
int dfs(int u,int flow) {
if(u==t||!flow) return flow;
inque[u]=1;
int tmp=flow;
for(int &i=cur[u]; ~i; i=e[i].nxt) {
int v=e[i].to,fl;
if(dis[v]==dis[u]+e[i].c&&!inque[v]&&e[i].w) {
int fl=dfs(v,min(tmp,e[i].w));
if(fl) cost+=fl*e[i].c,tmp-=fl,e[i].w-=fl,e[i^1].w+=fl;
if(!tmp) {inque[u]=0;return flow;}
}
}
inque[u]=0;
if(tmp==flow) inque[u]=1;
return flow-tmp;
}
int dinic() {
int ans=0,fl;
while(spfa()) {
memcpy(cur,head,sizeof(head));
while(fl=dfs(s,INT_MAX)) ans+=fl;
}
return ans;
}
int main() {
cin>>n>>m;
memset(head,-1,sizeof(head));
s=20001,t=20002;
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) cin>>a[i][j];
for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) {
int c=((i+j)%2)^1;
if(c) {
for(int k=0; k<=3; k++) {
int tx=i+dx[k],ty=j+dy[k];
if(tx<1||tx>n||ty<1||ty>m) continue;
add(turn(i,j,k),turn(tx,ty,k^1),1,0);
}
}
mx+=count(a[i][j]);
if(a[i][j]==1) {//0001
if(c) {
add(s,turn(i,j,0),1,0);
add(turn(i,j,0),turn(i,j,1),1,2);
add(turn(i,j,0),turn(i,j,2),1,1);
add(turn(i,j,0),turn(i,j,3),1,1);
} else {
add(turn(i,j,0),t,1,0);
add(turn(i,j,1),turn(i,j,0),1,2);
add(turn(i,j,2),turn(i,j,0),1,1);
add(turn(i,j,3),turn(i,j,0),1,1);
}
} else if(a[i][j]==2) {//0010
if(c) {
add(s,turn(i,j,3),1,0);
add(turn(i,j,3),turn(i,j,2),1,2);
add(turn(i,j,3),turn(i,j,1),1,1);
add(turn(i,j,3),turn(i,j,0),1,1);
} else {
add(turn(i,j,3),t,1,0);
add(turn(i,j,2),turn(i,j,3),1,2);
add(turn(i,j,1),turn(i,j,3),1,1);
add(turn(i,j,0),turn(i,j,3),1,1);
}
} else if(a[i][j]==3) {//0011
if(c) {
add(s,turn(i,j,3),1,0);
add(s,turn(i,j,0),1,0);
add(turn(i,j,3),turn(i,j,2),1,1);
add(turn(i,j,0),turn(i,j,1),1,1);
} else {
add(turn(i,j,3),t,1,0);
add(turn(i,j,0),t,1,0);
add(turn(i,j,2),turn(i,j,3),1,1);
add(turn(i,j,1),turn(i,j,0),1,1);
}
} else if(a[i][j]==4) {//0100
if(c) {
add(s,turn(i,j,1),1,0);
add(turn(i,j,1),turn(i,j,0),1,2);
add(turn(i,j,1),turn(i,j,2),1,1);
add(turn(i,j,1),turn(i,j,3),1,1);
} else {
add(turn(i,j,1),t,1,0);
add(turn(i,j,0),turn(i,j,1),1,2);
add(turn(i,j,2),turn(i,j,1),1,1);
add(turn(i,j,3),turn(i,j,1),1,1);
}
} else if(a[i][j]==5) {//0101
if(c) {
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,0),1,0);
} else {
add(turn(i,j,1),t,1,0);
add(turn(i,j,0),t,1,0);
}
} else if(a[i][j]==6) {//0110
if(c) {
add(s,turn(i,j,3),1,0);
add(s,turn(i,j,1),1,0);
add(turn(i,j,3),turn(i,j,2),1,1);
add(turn(i,j,1),turn(i,j,0),1,1);
} else {
add(turn(i,j,3),t,1,0);
add(turn(i,j,1),t,1,0);
add(turn(i,j,2),turn(i,j,3),1,1);
add(turn(i,j,0),turn(i,j,1),1,1);
}
} else if(a[i][j]==7) {//0111
if(c) {
add(s,turn(i,j,0),1,0);
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,3),1,0);
add(turn(i,j,3),turn(i,j,2),1,2);
add(turn(i,j,1),turn(i,j,2),1,1);
add(turn(i,j,0),turn(i,j,2),1,1);
} else {
add(turn(i,j,0),t,1,0);
add(turn(i,j,1),t,1,0);
add(turn(i,j,3),t,1,0);
add(turn(i,j,2),turn(i,j,3),1,2);
add(turn(i,j,2),turn(i,j,1),1,1);
add(turn(i,j,2),turn(i,j,0),1,1);
}
} else if(a[i][j]==8) {//1000
if(c) {
add(s,turn(i,j,2),1,0);
add(turn(i,j,2),turn(i,j,3),1,2);
add(turn(i,j,2),turn(i,j,1),1,1);
add(turn(i,j,2),turn(i,j,0),1,1);
} else {
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),turn(i,j,2),1,2);
add(turn(i,j,1),turn(i,j,2),1,1);
add(turn(i,j,0),turn(i,j,2),1,1);
}
} else if(a[i][j]==9) {//1001
if(c) {
add(s,turn(i,j,2),1,0);
add(s,turn(i,j,0),1,0);
add(turn(i,j,2),turn(i,j,3),1,1);
add(turn(i,j,0),turn(i,j,1),1,1);
} else {
add(turn(i,j,2),t,1,0);
add(turn(i,j,0),t,1,0);
add(turn(i,j,3),turn(i,j,2),1,1);
add(turn(i,j,1),turn(i,j,0),1,1);
}
} else if(a[i][j]==10) {//1010
if(c) {
add(s,turn(i,j,2),1,0);
add(s,turn(i,j,3),1,0);
} else {
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),t,1,0);
}
} else if(a[i][j]==11) {//1011
if(c) {
add(s,turn(i,j,0),1,0);
add(s,turn(i,j,2),1,0);
add(s,turn(i,j,3),1,0);
add(turn(i,j,0),turn(i,j,1),1,2);
add(turn(i,j,2),turn(i,j,1),1,1);
add(turn(i,j,3),turn(i,j,1),1,1);
} else {
add(turn(i,j,0),t,1,0);
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),t,1,0);
add(turn(i,j,1),turn(i,j,0),1,2);
add(turn(i,j,1),turn(i,j,2),1,1);
add(turn(i,j,1),turn(i,j,3),1,1);
}
} else if(a[i][j]==12) {//1100
if(c) {
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,2),1,0);
add(turn(i,j,1),turn(i,j,0),1,1);
add(turn(i,j,2),turn(i,j,3),1,1);
} else {
add(turn(i,j,1),t,1,0);
add(turn(i,j,2),t,1,0);
add(turn(i,j,0),turn(i,j,1),1,1);
add(turn(i,j,3),turn(i,j,2),1,1);
}
} else if(a[i][j]==13) {//1101
if(c) {
add(s,turn(i,j,0),1,0);
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,2),1,0);
add(turn(i,j,2),turn(i,j,3),1,2);
add(turn(i,j,1),turn(i,j,3),1,1);
add(turn(i,j,0),turn(i,j,3),1,1);
} else {
add(turn(i,j,0),t,1,0);
add(turn(i,j,1),t,1,0);
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),turn(i,j,2),1,2);
add(turn(i,j,3),turn(i,j,1),1,1);
add(turn(i,j,3),turn(i,j,0),1,1);
}
} else if(a[i][j]==14) {//1110
if(c) {
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,2),1,0);
add(s,turn(i,j,3),1,0);
add(turn(i,j,1),turn(i,j,0),1,2);
add(turn(i,j,2),turn(i,j,0),1,1);
add(turn(i,j,3),turn(i,j,0),1,1);
} else {
add(turn(i,j,1),t,1,0);
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),t,1,0);
add(turn(i,j,0),turn(i,j,1),1,2);
add(turn(i,j,0),turn(i,j,2),1,1);
add(turn(i,j,0),turn(i,j,3),1,1);
}
} else {//1111
if(c) {
add(s,turn(i,j,0),1,0);
add(s,turn(i,j,1),1,0);
add(s,turn(i,j,2),1,0);
add(s,turn(i,j,3),1,0);
} else {
add(turn(i,j,0),t,1,0);
add(turn(i,j,1),t,1,0);
add(turn(i,j,2),t,1,0);
add(turn(i,j,3),t,1,0);
}
}
}
if(dinic()*2==mx) cout<<cost;
else cout<<-1;
return 0;
}
//left->down->right->up
//up->0,down->1,left->2,right->3
样例都过了，但只有1pts，其余全WA，求条
加载中...