博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj-3281(拆点+最大流)
阅读量:4313 次
发布时间:2019-06-06

本文共 921 字,大约阅读时间需要 3 分钟。

题意:有n头牛,f种食物,d种饮料,每头牛有自己喜欢的食物和饮料,问你最多能够几头牛搭配好,每种食物或者饮料只能一头牛享用;

解题思路:把牛拆点,因为流过牛的流量是由限制的,只能为1,然后,食物和牛的入点相连,牛的出点和饮料相连,求解最大流

代码:

#include
#include
#include
#include
#include
using namespace std;const int maxn=200500;const int inf=0x3f3f3f3f;struct Edge{ int fa; int next; int to; int w;}edge[maxn];int n,m,f,d;int head[maxn];int cnt,Start,End;int x,y,w;int depth[maxn];void add(int u,int v,int w){ //cout<
<<" "<
<
q; q.push(Start); depth[Start]=1; while(!q.empty()) { int temp=q.front(); q.pop(); for(int i=head[temp];i!=-1;i=edge[i].next) { int v=edge[i].to; if(depth[v]||edge[i].w<=0) continue; depth[v]=depth[temp]+1; q.push(v); } } return depth[End];//若为0表示没法到达也就是没有路径了;}int dfs(int u,int maxflow){ if(u==End) return maxflow; int add=0; for(int i=head[u];i!=-1&&add

  

转载于:https://www.cnblogs.com/huangdao/p/9965896.html

你可能感兴趣的文章
Entity Framework 4.3.1 级联删除
查看>>
codevs 1163:访问艺术馆
查看>>
冲刺Noip2017模拟赛3 解题报告——五十岚芒果酱
查看>>
并查集
查看>>
sessionStorage
查看>>
代码示例_进程
查看>>
Java中关键词之this,super的使用
查看>>
人工智能暑期课程实践项目——智能家居控制(一)
查看>>
前端数据可视化插件(二)图谱
查看>>
kafka web端管理工具 kafka-manager【转发】
查看>>
获取控制台窗口句柄GetConsoleWindow
查看>>
Linux下Qt+CUDA调试并运行
查看>>
51nod 1197 字符串的数量 V2(矩阵快速幂+数论?)
查看>>
OKMX6Q在ltib生成的rootfs基础上制作带QT库的根文件系统
查看>>
zabbix
查看>>
多线程基础
查看>>
完美解决 error C2220: warning treated as error - no ‘object’ file generated
查看>>
使用SQL*PLUS,构建完美excel或html输出
查看>>
SQL Server数据库笔记
查看>>
X-Forwarded-For伪造及防御
查看>>