萌新刚学网络流求助
样例全过，0分WA。我太难了，求dalao帮助
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
namespace quick {
#define tp template<typename Type>
namespace in {
inline char getc() {
static char buf[1<<21],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}
inline int read(char *s) {
*s=getc();
while(isspace(*s)) {*s=getc();if(*s==EOF) return 0;}
while(!isspace(*s)&&*s!=EOF) {s++;*s=getc();}
*s='\0'; return 1;
}
tp inline int read(Type &x) {
x=0;bool k=false;char c=getc();
while(!isdigit(c)) {k|=(c=='-');c=getc();if(c==EOF) return 0;}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c^48);c=getc();}
x*=(k?-1:1); return 1;
}
template <typename Type,typename... Args>
inline int read(Type &&t,Args &&...args) {
return read(t)+read(args...);
}
}
using in::read;
namespace out {
char buf[1<<21];int p1=-1;const int p2=(1<<21)-1;
inline void flush() {
fwrite(buf,1,p1+1,stdout);
p1=-1;
}
inline void putc(const char &c) {
if(p1==p2) flush();
buf[++p1]=c;
}
inline void write(char *s) {
while(*s!='\0') putc(*s),s++;
}
inline void write(const char *s) {
while(*s!='\0') putc(*s),s++;
}
tp inline void write(Type x) {
static char buf[30];int p=-1;
if(x<0) {putc('-');x=-x;}
if(x==0) putc('0');
else for(;x;x/=10) buf[++p]=x%10+48;
for(;p!=-1;p--) putc(buf[p]);
}
inline void write(const char &c) {putc(c);}
template <typename Type,typename... Args>
inline void write(const Type &t,const Args &...args) {
write(t);write(args...);
}
}
using out::write;
using out::flush;
tp inline Type max(const Type &a,const Type &b) {
if(a<b) return b;
return a;
}
tp inline Type min(const Type &a,const Type &b) {
if(a<b) return a;
return b;
}
tp inline void swap(Type &a,Type &b) {
a^=b^=a^=b;
}
tp inline Type abs(const Type &a) {
return a>=0?a:-a;
}
#undef tp
}
using namespace quick;
const int maxn=2000+10,inf=0x3f3f3f3f;
int n,m;
namespace MCMF {
int s,t;
struct Edge {
int v,next,cap,flow,cost;
Edge(const int &v,const int &next,const int &cap,const int &flow,const int &cost)
:v(v),next(next),cap(cap),flow(flow),cost(cost) {}
Edge() {}
}e[maxn<<5];
int head[maxn<<3],cnt=1;
inline void AddEdge(const int &u,const int &v,const int &cap,const int &cost) {
e[++cnt]=Edge(v,head[u],cap,0,cost);
head[u]=cnt;
e[++cnt]=Edge(u,head[v],0,0,-cost);
head[v]=cnt;
write("u:",u,"->v:",v," cap:",cap," cost:",cost,'\n');
}
inline char Spfa(int &flow,int &cost) {
static int d[maxn<<5],a[maxn<<5],cur[maxn<<5];
static std::queue<int> q;
static char inq[maxn<<5];
memset(inq,0x00,sizeof inq);
memset(d,0x3f,sizeof d);
d[s]=0;q.push(s);inq[s]=0xff;a[s]=inf;cur[s]=0;
while(!q.empty()) {
int u=q.front();
q.pop();
inq[u]=0x00;
for(int i(head[u]);i;i=e[i].next) {
const int &v=e[i].v;
if(e[i].flow<e[i].cap&&d[u]+e[i].cost<d[v]) {
cur[v]=i;
d[v]=d[u]+e[i].cost;
a[v]=min(a[u],e[i].cap-e[i].flow);
if(~inq[v]) {
q.push(v);inq[v]=0xff;
}
}
}
}
if(d[t]==inf) return 0x00;
flow+=a[t];
cost+=a[t]*d[t];
for(int u(t);u!=s;u=e[cur[u]^1].v) {
e[cur[u]].flow+=a[t];
e[cur[u]^1].flow-=a[t];
}
return 0xff;
}
int Solve(int &cost) {
int flow=0;cost=0;
while(!~Spfa(flow,cost));
return flow;
}
}
using MCMF::s;
using MCMF::t;
using MCMF::AddEdge;
int id1(const int &x,const int &y) {
return (x-1)*m+y;
}
inline int id2(const int &x,const int &y) {
return x+y*n*m;
}
inline int id(const int &x,const int &y,const int &i) {
return id2(id1(x,y),i);
}
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int map[maxn],tot;
inline int popcount(int x) {
int cnt=0;
for(;x;x^=x&(-x)) cnt++;
return cnt;
}
void Connect() {
for(int i(1);i<=n;i++)
for(int j(1);j<=m;j++) {
if(id1(i,j)&1) AddEdge(s,id(i,j,4),inf,0);
else AddEdge(id(i,j,4),t,inf,0);
for(int k(0);k<4;k++) {
if(!(map[id1(i,j)]&(1<<k))) continue;
tot++;
if(id1(i,j)&1) AddEdge(id(i,j,4),id(i,j,k),1,0);
else AddEdge(id(i,j,k),id(i,j,4),1,0);
}//处理与源点汇点的连边
}
write('\n');
for(int i(1);i<=n;i++)
for(int j(1);j<=m;j++) {
if(!(id1(i,j)&1)) continue;
for(int k(0);k<4;k++) {
int x=i+dx[k],y=j+dy[k];
if(x<1||y<1||x>n||y>m) continue;
AddEdge(id(i,j,k),id(x,y,(k+2)%4),1,0);
}
}//处理相邻格子之间的连边
write('\n');
for(int i(1);i<=n;i++)
for(int j(1);j<=m;j++) {
if(!map[id1(i,j)]||map[id1(i,j)]==5||map[id1(i,j)]==10||map[id1(i,j)]==15)
continue;
if(id1(i,j)&1)
switch(popcount(map[id1(i,j)])) {
case 1:
for(int k(0);k<4;k++)
if(map[id1(i,j)]&(1<<k)) {
AddEdge(id(i,j,k),id(i,j,(k+1)%4),1,1);
AddEdge(id(i,j,k),id(i,j,(k+3)%4),1,1);
AddEdge(id(i,j,k),id(i,j,(k+2)%4),1,2);
}
break;
case 2:
for(int k(0);k<4;k++)
if(map[id1(i,j)]&(1<<k))
AddEdge(id(i,j,k),id(i,j,(k+2)%4),1,1);
break;
case 3:
for(int k(0);k<4;k++)
if(!(map[id1(i,j)]&(1<<k))) {
AddEdge(id(i,j,(k+2)%4),id(i,j,k),1,2);
AddEdge(id(i,j,(k+1)%4),id(i,j,k),1,1);
AddEdge(id(i,j,(k+3)%4),id(i,j,k),1,1);
}
break;
default:;
}
else
switch(popcount(map[id1(i,j)])) {
case 1:
for(int k(0);k<4;k++)
if(map[id1(i,j)]&(1<<k)) {
AddEdge(id(i,j,(k+1)%4),id(i,j,k),1,1);
AddEdge(id(i,j,(k+3)%4),id(i,j,k),1,1);
AddEdge(id(i,j,(k+2)%4),id(i,j,k),1,2);
}
break;
case 2:
for(int k(0);k<4;k++)
if(map[id1(i,j)]&(1<<k))
AddEdge(id(i,j,(k+2)%4),id(i,j,k),1,1);
break;
case 3:
for(int k(0);k<4;k++)
if(!(map[id1(i,j)]&(1<<k))) {
AddEdge(id(i,j,k),id(i,j,(k+2)%4),1,2);
AddEdge(id(i,j,k),id(i,j,(k+1)%4),1,1);
AddEdge(id(i,j,k),id(i,j,(k+3)%4),1,1);
}
break;
default:;
}
}
}
int main(void) {
#ifndef ONLINE_JUDGE
freopen("cir.in","r",stdin);
#endif
read(n,m);
for(int i(1);i<=n;i++)
for(int j(1);j<=m;j++)
read(map[id1(i,j)]);
s=n*m*5+1;
t=n*m*5+2;
write(s," ",t,'\n');
for(int i(1);i<=n;i++)
for(int j(1);j<=m;j++)
for(int k(0);k<=4;k++)
write("i==",i," j==",j," k==",k," id==",id(i,j,k),'\n');
Connect();
int flow,cost;
flow=MCMF::Solve(cost);
write((2*flow==tot)?cost:-1,'\n');
flush();
return 0;
}
加载中...