3504: [Cqoi2014]危桥

xiaoxiao2021-02-27  266

算是一个比较迷的题。。 首先暴力构图很容易啊,就是st连a1,a2连ed什么的 然后随便yy一下都知道会有问题,就是a1会流到b2那里 那这怎么办呢,翻了翻题解,说将b1,b2反过来就好了 证明自己去看官方的解题报告。。

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N=55; const int MAX=1<<30; int n,a1,a2,an,b1,b2,bn; char ss[N][N]; struct qq{int x,y,z,last;}s[N*N*2]; int num,last[N]; void init (int x,int y,int z,int z1) { num++; s[num].x=x;s[num].y=y;s[num].z=z; s[num].last=last[x]; last[x]=num; swap(x,y); num++; s[num].x=x;s[num].y=y;s[num].z=z1; s[num].last=last[x]; last[x]=num; } void bt () { num=1;memset(last,-1,sizeof(last)); for (int u=0;u<n;u++) for (int i=u+1;i<n;i++) { if (ss[u][i]=='O') init(u,i,1,1); if (ss[u][i]=='N') init(u,i,MAX,MAX); } } int st,ed; int h[N]; bool Bt () { memset(h,-1,sizeof(h));h[st]=1; queue<int> q; q.push(st); while (!q.empty()) { int x=q.front();q.pop(); for (int u=last[x];u!=-1;u=s[u].last) { int y=s[u].y; if (s[u].z>0&&h[y]==-1) { h[y]=h[x]+1; q.push(y); } } } return h[ed]!=-1; } int mymin (int x,int y){return x<y?x:y;} int dfs (int x,int f) { if (x==ed) return f; int s1=0; for (int u=last[x];u!=-1;u=s[u].last) { int y=s[u].y; if (s[u].z>0&&h[y]==h[x]+1&&s1<f) { int lalal=dfs(y,mymin(s[u].z,f-s1)); s1+=lalal; s[u].z-=lalal; s[u^1].z+=lalal; } } if (s1==0) h[x]=-1; return s1; } void solve() { bt(); init(st,a1,an,0);init(a2,ed,an,0); init(st,b1,bn,0);init(b2,ed,bn,0); int ans=0; while (Bt()) { ans=ans+dfs(st,MAX); } if (ans<an+bn) {printf("No\n");return ;} bt(); swap(b1,b2); init(st,a1,an,0);init(a2,ed,an,0); init(st,b1,bn,0);init(b2,ed,bn,0); ans=0; while (Bt()) ans=ans+dfs(st,MAX); if (ans<an+bn) {printf("No\n");return ;} printf("Yes\n"); return ; } int main() { while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF) { for (int u=0;u<n;u++) scanf("%s",ss[u]); st=n+1;ed=st+1; solve(); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-9201.html

最新回复(0)