在线ftp传网站文件,网站开发项目启动成本,wordpress 链接 弹窗,网站 png文章目录题目描述解析代码题目描述
Alice 和 Bob 居住在一个由 NN 座岛屿组成的国家#xff0c;岛屿被编号为 00 到 N-1N−1。某些岛屿之间有桥相连#xff0c;桥上的道路是双向的#xff0c;但一次只能供一人通行。其中一些桥由于年久失修成为危桥#xff0c;最多只能通行…
文章目录题目描述解析代码题目描述
Alice 和 Bob 居住在一个由 NN 座岛屿组成的国家岛屿被编号为 00 到 N-1N−1。某些岛屿之间有桥相连桥上的道路是双向的但一次只能供一人通行。其中一些桥由于年久失修成为危桥最多只能通行两次。
Alice 希望在岛屿 a1和 a2 之间往返 an次从 a1 到 a2再从 a2 到 a1 算一次往返。同时Bob 希望在岛屿 b1和 b2之间往返 bn次。这个过程中所有危桥最多通行两次其余的桥可以无限次通行。请问 Alice 和 Bob 能完成他们的愿望吗
解析
首先可以把往返看成单程危桥当成只能通过1次 建图方法和显然但是会忽略a1流向b2、b1流向a2的问题 一个很巧妙的解决办法是交换b1和b2再跑一次如果还是满流就是合法的
代码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N2600;
const int M1e9;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,s,t;
struct node{int to,nxt;ll cap;
}p[N*N*2];
int fi[N],cnt;
void addline(int x,int y,ll cap){
// printf(x%d y%d cap%lld\n,x,y,cap);p[cnt](node){y,fi[x],cap};fi[x]cnt;p[cnt](node){x,fi[y],0};fi[y]cnt;
}
int bel[N],cur[N];
queueintq;
int bfs(){memset(bel,0,sizeof(bel));bel[s]1;q.push(s);while(!q.empty()){int nowq.front();q.pop();//printf(now%d\n,now);for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;//printf( to%d\n,to);if(bel[to]||!p[i].cap) continue;//printf( ok\n);bel[to]bel[now]1;q.push(to);}}return bel[t];
}
ll dfs(int x,ll lim){if(xt||!lim) return lim;ll res0;for(int icur[x];~ilim;ip[i].nxt){int top[i].to;if(!p[i].cap||bel[to]!bel[x]1) continue;ll adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(!res) bel[x]-1;return res;
}
ll dinic(){ll tot0;while(bfs()){//printf(ok);while(ll tmpdfs(s,2e15)) tottmp;}
// printf(tot%lld\n,tot);return tot;
}
int a1,a2,an,b1,b2,bn;
char ss[60][60];
void build(){char c;memset(fi,-1,sizeof(fi));cnt-1;for(int i1;in;i){for(int j1;jn;j){css[i][j];if(cX) continue;else if(cN) addline(i,j,2e18);else addline(i,j,1);}}
}
int main(){while(scanf(%d%d%d%d%d%d%d,n,a1,a2,an,b1,b2,bn)!EOF){a1;a2;b1;b2;for(int i1;in;i){scanf( %s,ss[i]1);}sn1;tn2;build();addline(s,a1,an);addline(a2,t,an);addline(s,b1,bn);addline(b2,t,bn);if(dinic()!anbn){printf(No\n);continue;}build();addline(s,a1,an);addline(a2,t,an);addline(s,b2,bn);addline(b1,t,bn);if(dinic()!anbn) printf(No\n);else printf(Yes\n);}return 0;
}
/**/
