辽宁沈阳网站建设,罗湖在线,国外优秀网页设计作品,南宁企业宣传片制作题目#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id2007 一个点的高度一定不是0就是1。答案一定形如一个左上角的连通块全是0的点、一个右下角的连通块全是1的点。 注意从东到西还有从南到北的边也有用#xff01;因为不一定是一个阶梯形的#xff0c;还可以…题目https://www.lydsy.com/JudgeOnline/problem.php?id2007 一个点的高度一定不是0就是1。答案一定形如一个左上角的连通块全是0的点、一个右下角的连通块全是1的点。 注意从东到西还有从南到北的边也有用因为不一定是一个阶梯形的还可以拐来拐去只是一定是两个连通块罢了。 所以最小割一下那个分界线就行了。但会TLE。 #includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N500*5015,M4000*5015,INF2e65;
int n,t,bh[505][505],hd[N],xnt1,cur[N],to[M],nxt[M],cap[M];
int dfn[N],q[N],he,tl;
int Mn(int a,int b){return ab?a:b;}
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9)retret*10ch-0,chgetchar();return fx?ret:-ret;
}
void add(int x,int y,int z)
{to[xnt]y;nxt[xnt]hd[x];hd[x]xnt;cap[xnt]z;to[xnt]x;nxt[xnt]hd[y];hd[y]xnt;cap[xnt]0;
}
bool bfs()
{memset(dfn,0,sizeof dfn);dfn[0]1;q[hetl1]0;while(hetl){int kq[he];for(int ihd[k],v;i;inxt[i])if(cap[i]!dfn[vto[i]])dfn[v]dfn[k]1,q[tl]v;}return dfn[t];
}
int dinic(int cr,int flow)
{if(crt)return flow;int use0;for(int icur[cr],v;i;inxt[i])if(cap[i]dfn[vto[i]]dfn[cr]1){int tmpdinic(v,Mn(flow-use,cap[i]));if(!tmp)dfn[v]0;usetmp;cap[i]-tmp;cap[i^1]tmp;if(useflow)return use;}return use;
}
int main()
{nrdn();for(int i0;in;i)for(int j0;jn;j)bh[i][j]t;t--; int d;for(int i0;in;i)for(int j1;jn;j)drdn(),add(bh[i][j-1],bh[i][j],d);for(int i1;in;i)for(int j0;jn;j)drdn(),add(bh[i-1][j],bh[i][j],d);for(int i0;in;i)for(int j1;jn;j) drdn(),add(bh[i][j],bh[i][j-1],d);for(int i1;in;i)for(int j0;jn;j)drdn(),add(bh[i][j],bh[i-1][j],d);int ans0;while(bfs())memcpy(cur,hd,sizeof hd),ansdinic(0,INF);printf(%d\n,ans);return 0;
} View Code 可以转成最短路。注意边的方向。 学习了学长的不显式建图的方法。大概 dis[ ][ ] 记录的就是从起点走到格子的距离再记4个 dis[ ][ ] 表示它的周围4条边的容量之类的。 #includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N505,INF2e65;
int n,dis[5][N][N],ansINF;bool vis[N][N];
struct Node{int x,y,dis;Node(int a0,int b0,int d0):x(a),y(b),dis(d) {}bool operator (const Node b)const{return disb.dis;}
};
priority_queueNode q;
int Mn(int a,int b){return ab?a:b;}
int rdn()
{int ret0;bool fx1;char chgetchar();while(ch9||ch0){if(ch-)fx0;chgetchar();}while(ch0ch9)retret*10ch-0,chgetchar();return fx?ret:-ret;
}
void add(int x,int y,int d)
{if(ddis[4][x][y])dis[4][x][y]d,q.push(Node(x,y,d));
}
void dj()
{for(int i1;in;i)add(1,i,dis[0][1][i]);for(int i1;in;i)add(i,n,dis[1][i][n1]);while(q.size()){int xq.top().x,yq.top().y,dq.top().dis; q.pop();if(vis[x][y])continue; vis[x][y]1;if(xn)add(x1,y,ddis[0][x1][y]);//x1(up)if(y1)add(x,y-1,ddis[1][x][y]);if(x1)add(x-1,y,ddis[2][x-1][y]);//x-1(dn)if(yn)add(x,y1,ddis[3][x][y]);}for(int i1;in;i)ansMn(ans,dis[4][i][1]dis[1][i][1]);for(int i1;in;i)ansMn(ans,dis[4][n][i]dis[0][n1][i]);//n1
}
int main()
{nrdn();int dn1;for(int i1;id;i)for(int j1;jn;j)dis[0][i][j]rdn();//upfor(int i1;in;i)for(int j1;jd;j)dis[1][i][j]rdn();//leftfor(int i0;in;i)//0~n 1~n !!!for(int j1;jn;j)dis[2][i][j]rdn();//dnfor(int i1;in;i)for(int j0;jn;j)dis[3][i][j]rdn();//rightmemset(dis[4],0x3f,sizeof dis[4]);dj();printf(%d\n,ans);return 0;
} View Code转载于:https://www.cnblogs.com/Narh/p/10165510.html
