如何建图?

  最开始的问题就是,怎么表示一只牛有了食物和饮料呢?

  后来发现可以先将食物与牛匹配,牛再去和饮料匹配,实际上这就构成了三个层次。

  起点到食物层边的容量是1,食物层到奶牛层容量是1,奶牛层到饮料层容量是1,饮料层到终点容量是1。

  但是后来发现有一组hack数据:

  2 3 3

  3 3 1 2 3 1 2 3
  3 3 1 2 3 1 2 3

  我们发现一头奶牛居然吃了多个套餐,所以要解决这个只需要将自己与自己建立一条容量是1的边就行了。

  

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
#define sc scanf
#define pt printf
#define maxe 40960
#define maxv 405
#define maxn 1000
#define mll long long
const int inf = 0x3f3f3f3f;
int mn(int a,int b) { return a<b?a:b; }
int s,t, N,F,D;
typedef struct ed{
int v,w,cap,flow;
} ed;
ed e[maxe];
int head[maxv],nxt[maxe],tot,dis[maxv];
void init()
{
tot = ;
memset(head,-,sizeof(head));
} void add(int u,int v,int cap,int flow)
{
e[tot].v=v;
e[tot].cap=cap;
e[tot].flow=flow;
nxt[tot]=head[u];
head[u]=tot++; e[tot].v=u;
e[tot].cap=flow;
e[tot].flow=;
nxt[tot]=head[v];
head[v]=tot++;
}
int dfs(int u,int exp)
{
if(exp==||u==t) return exp;
int i,v,flow=,tmp;
for(i=head[u];i!=-;i=nxt[i])
{
v=e[i].v;
//pt("u=%d,v=%d\n",u,v); if(dis[v]==dis[u]+)
{
tmp = dfs(v,mn(e[i].cap-e[i].flow,exp));
if(tmp==) continue;
// pt("u=%d,v=%d,tmp=%d\n",u,v,tmp);
e[i].flow += tmp;
e[i^].flow -= tmp; exp-=tmp;
flow+=tmp; if(exp==) break;
}
}
//pt("wt\n");
if(flow==) dis[u]=inf;
return flow;
}
stack<int> q;
int main()
{
freopen("in.txt","r",stdin);
while(~sc("%d%d%d",&N,&F,&D))
{
//pt("OK\n");
int i,j,ans=,u,v,tt,FF,DD;
init(); s=,t=+*N+F+D;
// pt("OK\n");
// F使用1-F N使用(F+1 - F+N)(F+1 + N - F+ 2*N) D使用 F+2*N+1 - F+2*N+D
for(i=;i<=F;++i) add(,i,,);
for(i=F+*N+;i<=F+*N+D;++i) add(i,t,,);
for(i=F+;i<=F+N;++i) add(i,i+N,,);
//pt("OK\n");
for(i=;i<=N;++i)
{
sc("%d%d",&FF,&DD);
for(j=;j<=FF;++j)
{
sc("%d",&tt);
add(tt,F+i,,);
}
for(j=;j<=DD;++j)
{
sc("%d",&tt);
add(F+N+i,F+*N+tt,,);
}
}
//pt("OK\n");
while()
{
//BFS建立层次图
memset(dis,inf,sizeof(dis));
dis[s]=;
while(!q.empty()) q.pop();
q.push(s);
while(!q.empty())
{ u=q.top(); q.pop();
for(i=head[u];i!=-;i=nxt[i])
{
if(e[i].cap - e[i].flow <= ) continue;
v = e[i].v; if(dis[u]+<dis[v])
{
dis[v] = dis[u] +;
//pt("BFS: u=%d,v=%d\n",u,v);
if(v==t) break;
q.push(v);
} }
}
if(dis[t]==inf) break;
//DFS进行增广
tt=dfs(,inf);
if(tt==) break;
else ans+=tt;
//pt("tt=%d\n",tt); }
pt("%d\n",ans);
}
return ;
}

POJ 3281

最新文章

  1. web api添加拦截器
  2. Dynamic CRM 查询实体记录 被共享给了 哪个用户
  3. 0103MySQL中的B-tree索引 USINGWHERE和USING INDEX同时出现
  4. asp.net发送E-mail
  5. ios 游戏《魂斗罗》 AL文件素材破解
  6. python bottle框架(WEB开发、运维开发)教程
  7. [置顶] 局部加权回归、最小二乘的概率解释、逻辑斯蒂回归、感知器算法——斯坦福ML公开课笔记3
  8. 对Extjs中store的多种操作
  9. Linux下好用的简单实用命令
  10. 英语背单词app
  11. TCP连接与释放
  12. TNetHTTPClient 使用
  13. W phase 学习
  14. Jenkins入门-部署gitlab 项目(8)
  15. leetcode1009
  16. GoogLeNetv3 论文研读笔记
  17. logstash获取日志,时间戳相差8小时
  18. js数组push方法使用注意
  19. Simple2D-14(音乐播放器)简介
  20. container,algorith,iterate

热门文章

  1. JS 总结之关于 this 应该知道的几个点
  2. POJ3321[苹果树] 树状数组/线段树 + dfs序
  3. 工作时使用的vim配置
  4. [ASP.NET Core 3框架揭秘] 依赖注入:依赖注入模式
  5. asp.net core2.1认证和授权解密
  6. spark浅谈(2):SPARK核心编程
  7. c# 读取二进制文件并转换为 16 进制显示
  8. sqli-5&amp;6
  9. Spring Data Elasticsearch 用户指南
  10. 黑客已经瞄准5G网络,如何防止LTE网络攻击?