锐客网

  1. 首页 > it技术 > >

省选专练[TJOI2013]循环格

省选专练[TJOI2013]循环格
文章图片

神仙网络流QAQ
这个主要还是没想通
环是啥：图中全是入读出度为1的点
所以用费用流表示改变方向

#include using namespace std; const int N=1e5+10; const int INF=0x3f3f3f3f; struct Front_star{ int u,v,w,c,nxt; }e[N<<2]; int cnt=1; int first[N]={}; void addedge(int u,int v,int w,int c){ cnt++; e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].c=c; e[cnt].nxt=first[u]; first[u]=cnt; } void add(int u,int v,int w,int c){ addedge(u,v,w,c); addedge(v,u,0,-c); } int R,C; int idx[21][21]={}; int idxcnt=0; int pos[21][21]={}; int S=0,T=1001; int dx[5]={0,0,0,-1,1}; int dy[5]={0,-1,1,0,0}; map mmp; void Build_Gra(){ for(int i=1; i<=R; i++){ for(int j=1; j<=C; j++){ idx[i][j]=++idxcnt; } } for(int i=1; i<=R; i++){ for(int j=1; j<=C; j++){ for(int k=1; k<=4; k++){ int xx=i+dx[k]; int yy=j+dy[k]; xx=(xx-1+R)%R+1; yy=(yy-1+C)%C+1; add(idx[i][j],idx[xx][yy]+R*C,1,(pos[i][j]==k?0:1)); } } } for(int i=1; i<=R; i++){ for(int j=1; j<=C; j++){ add(S,idx[i][j],1,0); add(idx[i][j]+R*C,T,1,0); } } } queue Q; int inqueue[N]={}; int dis[N]={}; int pre[N]={}; bool SPFA(){ for(int i=S; i<=T; ++i)dis[i]=INF,pre[i]=0; dis[S]=0; Q.push(S); while(!Q.empty()){ int x=Q.front(); Q.pop(); inqueue[x]=0; for(int i=first[x]; i; i=e[i].nxt){ int v=e[i].v; if(e[i].w&&e[i].c+dis[x]

【省选专练[TJOI2013]循环格】转载于:https://www.cnblogs.com/Leo-JAM/p/10079146.html

    推荐阅读


    上一篇：Vue列表渲染

    下一篇：自定义progressbar 的思路