BZOJ4205: 卡牌配对
Aug 18, 2015 08:39:03 PM
题解:
首先暴力连边匹配肯定是不行的...
由于$200$以内的质数仅有$46$个,我们构造三类点$ab(p_1,p_2),ac(p_1,p_2),bc(p_1,p_2)$分别表示参数1能被$p_1$整除,参数2能被$p_2$整除,剩下的依此类推.
然后对于左侧的点向符合条件的中间点连边.
对于右侧的点从符合条件的中间点连边.
这样做事实上是边分组,很显然是正确的.
直接用dinic玩就行了.
代码:
#include<cstdio> #include<cctype> #include<cstring> #include<climits> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define inf 0x3f3f3f3f struct Solver{ static const int V=100010; static const int E=3000010; int head[V],next[E],flow[E],end[E],ind,d[V]; inline void reset(){ memset(head,-1,sizeof head); ind=0; } inline void addedge(int a,int b,int f){ int q=ind++; end[q]=b; next[q]=head[a]; head[a]=q; flow[q]=f; } inline void make(int a,int b,int f){ addedge(a,b,f); addedge(b,a,0); } inline bool bfs(int s,int t){ static int q[V]; int fr=0,ta=0; memset(d,-1,sizeof d); d[q[ta++]=s]=0; while(fr!=ta){ int i=q[fr++]; for(int j=head[i];j!=-1;j=next[j]) if(flow[j]&&d[end[j]]==-1) d[q[ta++]=end[j]]=d[i]+1; } return d[t]!=-1; } inline int dinic(int p,int t,int Maxflow){ if(p==t) return Maxflow; int last=Maxflow; for(int j=head[p];j!=-1;j=next[j]) if(flow[j]&&d[end[j]]==d[p]+1){ int to=dinic(end[j],t,flow[j]>last?last:flow[j]); if(to){ flow[j]-=to; flow[j^1]+=to; if(!(last-=to)) return Maxflow; } } d[p]=-1; return Maxflow-last; } inline int Maxflow(int s,int t){ int re=0; while(bfs(s,t)) re+=dinic(s,t,inf); return re; } }g; #define N 210 int p[N],cnt; bool np[N]; inline void pre(){ int i,j; for(i=2;i<=200;++i){ if(!np[i]) p[++cnt]=i; for(j=1;j<=cnt&&p[j]*i<=200;++j){ np[i*p[j]]=1; if(i%p[j]==0) break; } } } int a[51][51],b[51][51],c[51][51]; int x[2][30010],y[2][30010],z[2][30010]; vector<int>v[N]; int main(){ pre(); int n,m; cin>>n>>m; int i,j,k; for(i=1;i<=n;++i) scanf("%d%d%d",&x[0][i],&y[0][i],&z[0][i]); for(i=1;i<=m;++i) scanf("%d%d%d",&x[1][i],&y[1][i],&z[1][i]); for(i=1;i<=200;++i) for(j=1;j<=cnt;++j) if(i%p[j]==0) v[i].push_back(j); int id=n+m; for(i=1;i<=cnt;++i) for(j=1;j<=cnt;++j){ a[i][j]=++id; b[i][j]=++id; c[i][j]=++id; } int s=0,t=++id; g.reset(); for(i=1;i<=n;++i) g.make(s,i,1); for(i=1;i<=m;++i) g.make(n+i,t,1); int p,q; for(i=1;i<=n;++i){ for(j=0;j<v[x[0][i]].size();++j) for(k=0;k<v[y[0][i]].size();++k){ p=v[x[0][i]][j]; q=v[y[0][i]][k]; g.make(i,a[p][q],1); } for(j=0;j<v[x[0][i]].size();++j) for(k=0;k<v[z[0][i]].size();++k){ p=v[x[0][i]][j]; q=v[z[0][i]][k]; g.make(i,b[p][q],1); } for(j=0;j<v[y[0][i]].size();++j) for(k=0;k<v[z[0][i]].size();++k){ p=v[y[0][i]][j]; q=v[z[0][i]][k]; g.make(i,c[p][q],1); } } for(i=1;i<=m;++i){ for(j=0;j<v[x[1][i]].size();++j) for(k=0;k<v[y[1][i]].size();++k){ p=v[x[1][i]][j]; q=v[y[1][i]][k]; g.make(a[p][q],n+i,1); } for(j=0;j<v[x[1][i]].size();++j) for(k=0;k<v[z[1][i]].size();++k){ p=v[x[1][i]][j]; q=v[z[1][i]][k]; g.make(b[p][q],n+i,1); } for(j=0;j<v[y[1][i]].size();++j) for(k=0;k<v[z[1][i]].size();++k){ p=v[y[1][i]][j]; q=v[z[1][i]][k]; g.make(c[p][q],n+i,1); } } cout<<g.Maxflow(s,t)<<endl; return 0; }
BZOJ1443: [JSOI2009]游戏Game 二分图+博弈论+网络流
Mar 06, 2015 02:08:04 PM
思路:
首先将图黑白二染色变成二分图.
然后求出一组最大匹配.
如果某个点不在匹配中,那么先手选择这个点.
那么后手只能走向一个匹配点(否则就不是最大匹配了).于是先手就可以沿着匹配边走回来.
那么此时如果后手还能走的话,就必定走到一个匹配点上.(否则就存在增广路了).于是先手又沿着匹配边走回来.
最后总是后手无路可走.因此先手必胜.
因此如果某个点不是最大匹配的必须点.就可以选择这个点.
如何找出这个呢?
在残量网络上,从\(S\)出发能够遍历到的左端的点,以及从\(T\)出发能够反向遍历到的右端的点.
证明的话,就是如果能够遍历到,就证明可以被换掉,而使得匹配数不减少.(稍微脑补一下)
(注意总点数要开2W,我不知道为什么)
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define INF ~0U>>1 struct Solver{ static const int V=20010; static const int E=V<<2; int head[V],next[E],end[E],flow[E],ind; int gap[V],d[V],stk[V],top,cur[V]; inline void reset(){ ind=top=0,memset(head,-1,sizeof head); } inline void addedge(int a,int b,int f){ int q=ind++; end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f; } inline void make(int a,int b,int f){ //printf("%d %d %d\n",a,b,f); addedge(a,b,f),addedge(b,a,0); } inline void bfs(int T){ static int q[V]; int fr=0,ta=0; memset(d,-1,sizeof d),memset(gap,0,sizeof gap),++gap[d[T]=0],q[ta++]=T; while(fr^ta){ int i=q[fr++]; for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1) ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j]; } } inline int Maxflow(int S,int T){ int re=0,ins,Min,i,u=S; bfs(T),memcpy(cur,head,sizeof cur); while(d[S]<T-S+1){ if(u==T){ for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])Min=flow[stk[i]],ins=i; for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min; u=end[stk[top=ins]^1]; } if(u!=T&&!gap[d[u]-1])break; bool find=0; for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){ find=1,ins=j;break; } if(find){ stk[top++]=cur[u]=ins,u=end[ins]; } else{ Min=T-S+1; for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min) cur[u]=j,Min=d[end[j]]; if(!--gap[d[u]])break; ++gap[d[u]=Min+1]; if(u!=S)u=end[stk[--top]^1]; } } return re; } }Stg; #define N 110 char s[N]; int lab[N][N],x[N*N],y[N*N]; int res[N*N],nums; bool vis[N*N]; inline void bfs(int S,bool rev){ static int q[N*N]; int fr=0,ta=0; memset(vis,0,sizeof vis),vis[S]=1,q[ta++]=S; while(fr^ta){ int i=q[fr++]; for(int j=Stg.head[i];j!=-1;j=Stg.next[j])if(Stg.flow[j^rev]&&!vis[Stg.end[j]]) vis[Stg.end[j]]=1,q[ta++]=Stg.end[j]; } } int main(){ int n,m;scanf("%d%d",&n,&m); register int i,j; int cnt=0; for(i=1;i<=n;++i){ scanf("%s",s+1); for(j=1;j<=m;++j)if(s[j]!='#')lab[i][j]=++cnt,x[cnt]=i,y[cnt]=j; } int S=0,T=cnt+1,num0=0,num1=0; Stg.reset(); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]){ if((i+j)&1){ ++num1; Stg.make(S,lab[i][j],1); if(lab[i-1][j])Stg.make(lab[i][j],lab[i-1][j],INF); if(lab[i+1][j])Stg.make(lab[i][j],lab[i+1][j],INF); if(lab[i][j-1])Stg.make(lab[i][j],lab[i][j-1],INF); if(lab[i][j+1])Stg.make(lab[i][j],lab[i][j+1],INF); } else ++num0,Stg.make(lab[i][j],T,1); } if(num0==0&&num1==0){ puts("LOSE"); return 0; } int re=Stg.Maxflow(S,T); /*for(i=S;i<=T;++i)for(j=Stg.head[i];j!=-1;j=Stg.next[j]) printf("%d %d %d\n",i,Stg.end[j],Stg.flow[j]);*/ if(num0==num1&&re==num0){ puts("LOSE"); return 0; } puts("WIN"); bfs(S,0); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)&1)&&vis[lab[i][j]])res[++nums]=lab[i][j]; bfs(T,1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(lab[i][j]&&((i+j)%2==0)&&vis[lab[i][j]])res[++nums]=lab[i][j]; sort(res+1,res+nums+1); for(i=1;i<=nums;++i){ printf("%d %d\n",x[res[i]],y[res[i]]); } return 0; }
BZOJ1570:[JSOI2008]Blue Mary的旅行 暴力+网络流
Mar 06, 2015 02:05:50 PM
思路:
暴力枚举答案,然后将点分层,边总是从该层连向下一层.
然后判断最大流是不是满足题意.
具体连边看代码.
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define INF ~0U>>1 struct Solver{ static const int V=50*100; static const int E=2450*100*2; int head[V],next[E],end[E],flow[E],ind; int d[V],gap[V],stk[V],top,cur[V]; inline void reset(){ ind=top=0,memset(head,-1,sizeof head); } inline void addedge(int a,int b,int f){ int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f; } inline void make(int a,int b,int f){ /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0); } inline void bfs(int T){ static int q[V];int fr=0,ta=0; memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++gap[d[T]=0],q[ta++]=T; while(fr^ta){ int i=q[fr++]; for(int j=head[i];j!=-1;j=next[j])if(d[end[j]]==-1) ++gap[d[end[j]]=d[i]+1],q[ta++]=end[j]; } } inline int Maxflow(int S,int T){ bfs(T),memcpy(cur,head,sizeof cur); int re=0,Min,ins,i,u=S; while(d[S]<T-S+1){ if(u==T){ for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]]; for(re+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min; u=end[stk[top=ins]^1]; } if(u!=T&&!gap[d[u]-1])break; bool find=0; for(int&j=cur[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]+1==d[u]){ find=1,ins=j;break; } if(find){stk[top++]=cur[u]=ins,u=end[ins];} else{ Min=T-S+1; for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min) cur[u]=j,Min=d[end[j]]; if(!--gap[d[u]])break; ++gap[d[u]=Min+1]; if(u!=S)u=end[stk[--top]^1]; } } return re; } }Stg; struct Edge{ int u,v,f; }E[2510]; #define get(x,dep) ((dep-1)*n+x) int main(){ int n,m,T;scanf("%d%d%d",&n,&m,&T); register int i,j; for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f); int re; for(re=1;;++re){ Stg.reset(); for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f); for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF); for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF); int now=Stg.Maxflow(0,n*(re+1)+1); //printf("%d\n",now); if(now>=T)break; } printf("%d\n",re); return 0; }
BZOJ1189:[HNOI2007]紧急疏散evacuate 二分+最大流
Feb 08, 2015 04:59:56 PM
思路:
首先bfs求出每个空地到每个门的最短距离,注意中间不能经过任何门.好像是原题说过只要经过门就算是退出了.
随后我们二分答案,从原点到每块空地连容量为1的边,从每扇门到汇点连容量为(当前二分的答案)时间的边,对于每块空地和每扇门,若距离不超过时间,则从空地到门连一条容量为1的边.
好像唯一的trick就是从门到汇点的边?不过大家自己YY一下吧.
反正不难.
#include<cstdio> #include<cstring> #include<queue> #include<cctype> #include<iostream> #include<algorithm> using namespace std; #define INF 0x3f3f3f3f #define N 21 #define M 21 int n,m; char s[M]; int ty[N][M]; int d[N][M]; static const int dx[]={-1,1,0,0},dy[]={0,0,1,-1}; struct Ins{ int x,y; Ins(){} Ins(int _x,int _y):x(_x),y(_y){} }; void bfs(int x,int y){ static queue<Ins>q; d[x][y]=0,q.push(Ins(x,y)); while(!q.empty()){ Ins tmp=q.front();q.pop(); for(int k=0;k<4;++k){ int nx=tmp.x+dx[k],ny=tmp.y+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&ty[nx][ny]==1&&d[nx][ny]==-1) d[nx][ny]=d[tmp.x][tmp.y]+1,q.push(Ins(nx,ny)); } } } struct MaxflowSolver{ static const int V=1010,E=200010; int head[V],next[E],end[E],flow[E],ind,d[V],inq[V]; inline void reset(){ind=0,memset(head,-1,sizeof head);} inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;} inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);} inline bool bfs(int S,int T){ static int q[V];int fr=0,ta=0; memset(d,-1,sizeof d),d[S]=0,q[ta++]=S; while(fr^ta){ int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j]; }return d[T]!=-1; } inline int dinic(int p,int T,int Maxflow){ if(p==T)return Maxflow; int last=Maxflow; for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){ int to=dinic(end[j],T,last>flow[j]?flow[j]:last); if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;} }d[p]=-1;return Maxflow-last; } inline int Maxflow(int S,int T){ int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res; } }Stg; int lab[N][M]; int main(){ scanf("%d%d",&n,&m);register int i,j; for(i=1;i<=n;++i){ scanf("%s",s+1); for(j=1;j<=m;++j)if(s[j]=='.')ty[i][j]=1;else if(s[j]=='D')ty[i][j]=2; } int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j])lab[i][j]=++id; int L=0,R=1<<30,mid; while(L<R){ mid=(L+R)>>1; Stg.reset(); int cnt=0; for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==1)Stg.make(0,lab[i][j],1),++cnt; for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2)Stg.make(lab[i][j],n*m+1,mid); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(ty[i][j]==2){ memset(d,-1,sizeof d),bfs(i,j); for(int p=1;p<=n;++p)for(int q=1;q<=m;++q)if(ty[p][q]==1&&d[p][q]!=-1) if(d[p][q]<=mid)Stg.make(lab[p][q],lab[i][j],1); } if(Stg.Maxflow(0,n*m+1)==cnt)R=mid;else L=mid+1; } if(L==1<<30)puts("impossible");else printf("%d",L); return 0; }
BZOJ1822:[JSOI2010]Frozen Nova 冷冻波 二分+计算几何+网络流
Feb 07, 2015 09:10:58 AM
思路:
一眼网络流,套一个二分就行了.
关键是如何判断巫妖和精灵之间能否有圆阻挡.
一开始我是进行了复杂的判断:如果线段平行于x轴或者平行于y轴直接特判;
否则求出圆心到直线的距离,如果距离不超过半径,则用一个简单的公式求出圆心到直线最近点的横坐标,利用这个横坐标与线段两个端点的横坐标比较,得出结果.
可是数据跟我想的根本不是一回事啊啊啊!
根本只需要判断距离啊啊啊!!而且相切的情况不算相交啊啊啊!!
什么坑爹数据,我是领教到了.
#include<cstdio> #include<cstring> #include<climits> #include<iostream> #include<algorithm> using namespace std; typedef long long LL; #define INF 0x3f3f3f3f #define N 210 #define M 210 #define P 210 struct MaxflowSolver{ static const int V=410; static const int E=100010; int head[V],next[E],end[E],flow[E],ind,d[V]; inline void reset(){ind=0,memset(head,-1,sizeof head);} inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;} inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);} inline bool bfs(int S,int T){ static int q[V];int fr=0,ta=0; memset(d,-1,sizeof d),d[S]=0,q[ta++]=S; while(fr^ta){ int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j]; }return d[T]!=-1; } inline int dinic(int p,int T,int Maxflow){ if(p==T)return Maxflow; int last=Maxflow; for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==d[p]+1){ int to=dinic(end[j],T,last>flow[j]?flow[j]:last); if(to){flow[j]-=to,flow[j^1]+=to;if(!(last-=to))return Maxflow;} }d[p]=-1;return Maxflow-last; } inline int Maxflow(int S,int T){ int res=0;while(bfs(S,T))res+=dinic(S,T,INF);return res; } }Stg; int x1[N],y1[N],x2[M],y2[M],lim[N],cd[N],ox[P],oy[P],r[P]; int G[N][M]; inline int sqr(int x){return x*x;} int main(){ int n,m,p;scanf("%d%d%d",&n,&m,&p);register int i,j,k; for(i=1;i<=n;++i)scanf("%d%d%d%d",&x1[i],&y1[i],&lim[i],&cd[i]); for(i=1;i<=m;++i)scanf("%d%d",&x2[i],&y2[i]); for(i=1;i<=p;++i)scanf("%d%d%d",&ox[i],&oy[i],&r[i]); int a,b,c; for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(sqr(x1[i]-x2[j])+sqr(y1[i]-y2[j])<=sqr(lim[i])){ bool ok=1; for(k=1;k<=p&&ok;++k){ a=y1[i]-y2[j],b=x2[j]-x1[i],c=(x1[i]-x2[j])*y1[i]-(y1[i]-y2[j])*x1[i]; if((LL)(a*ox[k]+b*oy[k]+c)*(a*ox[k]+b*oy[k]+c)<(LL)r[k]*r[k]*(a*a+b*b))ok=0; } if(ok)G[i][j]=1; } int L=0,R=1<<30,mid; while(L<R){ mid=(L+R)>>1; Stg.reset(); for(i=1;i<=n;++i)Stg.make(0,i,mid/cd[i]+1); for(i=1;i<=m;++i)Stg.make(n+i,n+m+1,1); for(i=1;i<=n;++i)for(j=1;j<=m;++j)if(G[i][j])Stg.make(i,n+j,1); if(Stg.Maxflow(0,n+m+1)==m)R=mid;else L=mid+1; } if(L==1<<30)puts("-1");else printf("%d",L); return 0; }
BZOJ3774:最优选择 网络流
Feb 05, 2015 04:47:47 PM
思路:
首先由于是一个二分图,我们分为左右两部分.
...然后具体的建模自己看代码吧,真的是好神奇的思路...
我居然连这都想不出来真是混不下去了.
#include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> using namespace std; static const int INF=0x3f3f3f3f; struct MaxflowSolver{ static const int V=5010; static const int E=80010; int head[V],next[E],end[E],flow[E],ind; int d[V]; inline void reset(){ind=0,memset(head,-1,sizeof head);} inline void addedge(int a,int b,int f){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;} inline void make(int a,int b,int f){addedge(a,b,f),addedge(b,a,0);} inline bool bfs(int S,int T){ static int q[V];int fr=0,ta=0; memset(d,-1,sizeof d),d[S]=0,q[ta++]=S; while(fr^ta){ int i=q[fr++];for(int j=head[i];j!=-1;j=next[j])if(flow[j]&&d[end[j]]==-1)d[end[j]]=d[i]+1,q[ta++]=end[j]; }return d[T]!=-1; } inline int dinic(int p,int T,int Maxflow){ if(p==T)return Maxflow; int last=Maxflow; for(int j=head[p];j!=-1;j=next[j])if(flow[j]&&d[p]+1==d[end[j]]){ int to=dinic(end[j],T,last>flow[j]?flow[j]:last);if(to)flow[j]-=to,flow[j^1]+=to,last-=to; if(!last)return Maxflow; } d[p]=-1;return Maxflow-last; } inline int Maxflow(int S,int T){ int res=0; while(bfs(S,T))res+=dinic(S,T,INF); return res; } }Stg; int lab[51][51][2],a[51][51],b[51][51]; const int dx[]={-1,1,0,0},dy[]={0,0,-1,1}; int main(){ int n,m;scanf("%d%d",&n,&m);register int i,j,k;int x,res=0; int id=0;for(i=1;i<=n;++i)for(j=1;j<=m;++j)lab[i][j][0]=++id,lab[i][j][1]=++id; for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&a[i][j]); for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&b[i][j]),res+=b[i][j]; int S=0,T=id+1; Stg.reset(); for(i=1;i<=n;++i)for(j=1;j<=m;++j){ if((i+j)&1)Stg.make(S,lab[i][j][0],a[i][j]),Stg.make(lab[i][j][0],lab[i][j][1],b[i][j]); else Stg.make(lab[i][j][1],lab[i][j][0],b[i][j]),Stg.make(lab[i][j][0],T,a[i][j]); for(k=0;k<4;++k){ int nowx=i+dx[k],nowy=j+dy[k]; if(nowx>=1&&nowx<=n&&nowy>=1&&nowy<=m){ if((i+j)&1)Stg.make(lab[i][j][0],lab[nowx][nowy][1],INF); else Stg.make(lab[nowx][nowy][1],lab[i][j][0],INF); } } } printf("%d",res-Stg.Maxflow(S,T)); return 0; }