LG1345 「USACO5.4」Telecowmunication 最小割
2024-10-18 11:11:33
问题描述
题解
点边转化,最小割,完事。
\(\mathrm{Code}\)
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
const int maxn=1007;
const int maxm=10007;
const int INF=0x3f3f3f3f;
int n,m,xx,yy;
int Head[maxn],to[maxm],w[maxm],Next[maxm],tot=1;
void add(int x,int y,int z){
to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;//错误笔记:如果我加边再不计边权,我就*****
}
int S,T,d[maxn];
bool bfs(){
memset(d,0,sizeof(d));
queue<int>q;q.push(S);d[S]=1;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=Head[x];i;i=Next[i]){
int y=to[i];
if(d[y]||!w[i]) continue;
q.push(y);d[y]=d[x]+1;
if(y==T) return true;
}
}
return false;
}
int dfs(int x,int flow){
if(x==T) return flow;
int rest=flow;
for(int i=Head[x];i&&rest;i=Next[i]){
int y=to[i];
if(d[y]!=d[x]+1||!w[i]) continue;
int k=dfs(y,min(rest,w[i]));
if(!k) d[y]=0;
else{
w[i]-=k,w[i xor 1]+=k;
rest-=k;
}
}
return flow-rest;
}
int main(){
read(n);read(m);read(xx);read(yy);
for(int i=1,x,y;i<=m;i++){
read(x);read(y);
add(x+n,y,INF);add(y,x+n,0);
add(y+n,x,INF);add(x,y+n,0);
}
for(int i=1;i<=n;i++){
add(i,i+n,1);add(i+n,i,0);
}
S=xx+n,T=yy;
int ans=0;
while(bfs()){
int t;
while(t=dfs(S,0x3f3f3f3f)) ans+=t;
}
printf("%d\n",ans);
return 0;
}
最新文章
- SSM整合(二):Spring4与Mybatis3整合
- bootstrap dialog 使用模态对话框
- PC远程调试移动设备
- [转载]基于TFS实践敏捷-工作项跟踪
- Java正则表达式的应用
- CF-358D-Dima and Hares【T^T+*^*】
- JS 执行环境与作用域链
- 一道来自华为的C机试题目
- Stat
- Android Game Examples
- js怎么判断浏览器类型
- GridView七十二绝技-大全(收藏版)(转至别人博客)
- Ubuntu16.04+cuda9.0+matlab+opencv3.3+caffe服务器配置(问题汇总)
- AspNetCoreMvc使用MongoDB,快来get一下吧。
- 网络通信协议,TCP和UDP 的区别
- vue生命周期、钩子函数
- Python内置函数之匿名(lambda)函数
- MongoDB副本集配置系列三:副本集的认证方式
- standby_file_management 参数为manual 导致ORA-01111问题
- mysql 5.5多实例部署
热门文章
- 拉丁方阵问题 -- python实现
- Dynamics 365 Customer Engagement导入解决方案时出错:Microsoft.Crm.CrmException: Plug-in assembly does not contain the required types or assembly content cannot be updated.
- n个数字相加
- 原生js放大镜效果
- java之类的构造方法
- LeetCode 652: 寻找重复的子树	Find Duplicate Subtrees
- VSCode 使用 ESLint + Prettier 来统一 JS 代码
- Jenkinsfile构建docker镜像
- Oracle - SPM固定执行计划(二)
- 启动jar包并生成日志的linux脚本