【USACO】Dining
2024-08-25 02:58:20
【题目链接】
【JZXX】点击打开链接
【caioj】点击打开链接
【算法】
拆点+网络流
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000 int i,tot,N,F,D,sf,sd,ans,x;
int U[MAXN*],V[MAXN*],W[MAXN*],Head[MAXN*],
Next[MAXN*],other[MAXN*],h[MAXN*]; template <typename T> void read(T &x) {
int f=; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c=='-') f=-; }
for (; isdigit(c); c = getchar()) x=x*+c-'';
x*=f;
} inline void add(int a,int b,int c) {
++tot;
U[tot] = a; V[tot] = b; W[tot] = c;
Next[tot] = Head[a]; Head[a] = tot;
other[tot] = tot + ;
++tot;
U[tot] = b; V[tot] = a; W[tot] = ;
Next[tot] = Head[b]; Head[b] = tot;
other[tot] = tot - ;
} inline bool BFS() {
int i,x,y;
queue<int> q;
memset(h,,sizeof(h));
h[] = ; q.push();
while (!q.empty()) {
x = q.front(); q.pop();
for (i = Head[x]; i; i = Next[i]) {
y = V[i];
if ((W[i] > ) && (!h[y])) {
h[y] = h[x] + ;
q.push(y);
}
}
}
if (h[F+*N+D+]) return true;
else return false;
} int maxflow(int x,int f) {
int i,y,s=,t;
if (x == F + * N + D + ) return f;
for (i = Head[x]; i; i = Next[i]) {
y = V[i];
if ((W[i] > ) && (h[y] == h[x] + ) && (s < f)) {
s += (t = maxflow(y,min(W[i],f-s)));
W[i] -= t; W[other[i]] += t;
}
}
if (!s) h[x] = ;
return s;
} int main() { read(N); read(F); read(D);
for (i = ; i <= F; i++) add(,+i,);
for (i = ; i <= D; i++) add(+F+*N+i,F+*N+D+,);
for (i = ; i <= N; i++) add(+F+i,+F+N+i,);
for (i = ; i <= N; i++) {
read(sf); read(sd);
while (sf--) {
read(x);
add(+x,i+F+,);
}
while (sd--) {
read(x);
add(+F+N+i,+F+*N+x,);
}
} while (BFS()) {
ans += maxflow(,2e9);
} cout<< ans << endl; return ; }
最新文章
- RPM方式安装MySQL5.6和windows下安装mysql解压版
- 解决Visual Studio 调试时候不能直接访问.json后缀文件的问题
- python笔记 - day4-之装饰器
- SuSE Apache2 VirtualHost Build
- [.ashx檔?泛型处理例程?]基础入门#2....FileUpload上传前,预览图片(两种作法--ashx与JavaScript)
- ubuntu 下添加sublime text 启动图标
- UpdatePanel局部刷新用法
- Python random模块sample、randint、shuffle、choice随机函数概念和应用
- SHA1withRSA加签名和验签名
- “指定的参数已超出有效值的范围”在【 parameterUpdate.Add(new OracleParameter(";STATUS";, 0));】报错
- shell+curl监控网站页面(域名访问状态),并利用sendemail发送邮件
- 用命令行发布android程序
- 二分法检索(binary search)(又名二进制搜索)
- E325 注意 发现交换文件
- nmap 端口扫描工具
- TClientDataSet的 AddIndex
- Audition CS6在Win 7中“音频输入的采样频率与输出设备不匹配”问题的解决 - imsoft.cnblogs
- 封装CoreGraphics的API简化绘图操作
- PHPstorm配置PHPunit对composer引入的php代码进行单元测试
- jQuery操作CheckBox的方法(选中,取消,取值)
热门文章
- android与服务器交互总结(json,post,xUtils,Volley)
- PS 如何使用钢笔工具
- Push flow
- nagios插件之登陆SBC监控电话数
- hadoop集群搭建datenode为0问题的解决
- 【每日Scrum】第五天(4.26) TD学生助手Sprint2站立会议
- 【程序猿联盟】官网上线啦!coderunity.com
- Kubernetes对象之Service
- Ubuntu 16.04 引导修复(Boot Repair)----lianwang----anzhuang windows hou(双系统修复一)
- Jquery源码分析-整体结构