//题目给出T,表示测试组数,n和m表示一共n和人,和m中贴纸。 //接下来n行,第一个是k,表示这个人的贴画种数,接下来有k //个数,表示不同种贴画的个数,求第一个人经过交换贴画,最多 //可以有多少种贴画,交换规则,一对一,对方没有这张才可以交换。 //分析: //第一个人当源点,得到的当汇点,每种贴画看做一个点,源点到这些点 //的容量为对应贴画的数量,每个人也看做一个点,弧上的容量为 //可以交换的张数,最后每个贴画到汇点 //的容量为1,求最大流,就是要求的结果。 #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxn = 100 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 void ClearAll(int n) { for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void ClearFlow() { for(int i = 0; i < edges.size(); i++) edges[i].flow = 0; } void AddEdge(int from, int to, int cap) { edges.push_back((Edge){from, to, cap, 0}); edges.push_back((Edge){to, from, 0, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } }; Dinic g; int main() { int T, n, m; scanf("%d", &T); for(int kase = 1; kase <= T; kase++) { scanf("%d%d", &n, &m); g.ClearAll(n+m+1); // s=0, 物品为结点1~m, 除Bob外的人为结点m+1~m+n-1,t=m+n for(int i = 0; i < n; i++) { int k, kind; scanf("%d", &k); vector<int> cnt(m+1, 0); for(int j = 0; j < k; j++) { scanf("%d", &kind); cnt[kind]++; } if(i == 0) { // Bob for(int j = 1; j <= m; j++) if(cnt[j] >= 1) g.AddEdge(0, j, cnt[j]); // s连边到物品 } else { // 其他人 for(int j = 1; j <= m; j++) { if(cnt[j] >= 2) g.AddEdge(m+i, j, cnt[j]-1); // 此人可以给出cnt[j]-1个物品j else if(cnt[j] == 0) g.AddEdge(j, m+i, 1); // 此人可以接受1个物品j } } } for(int i = 1; i <= m; i++) g.AddEdge(i, m+n, 1); printf("Case #%d: %d\n", kase, g.Maxflow(0, m+n)); } return 0; }
相关推荐
LogCollector是一套基于ETL数据分析模型的分布式数据流系统,同时适用于云域内网数据传送和跨云数据传送;同时支持Windows和Linux双系统平台(内置JRE8.X);同时支持实时传送、离线传送和断点续传;同时支持组件化...
lucene collector的使用 lucen分组统计 collector
weka可用的版本,很不错,集成了很多算法
LogCollector 一个收集 app 输出日志的工具,输出文件:模拟器是 /sdcard/Android/data/项目包名/cache/,真机是 /Android/data/项目包名/cache/,里面的 crash 目录是崩溃日志,log 目录是 logcat 日志。 如何使用 ...
datacollector, StreamSets DataCollector连续大数据摄取基础架构 什么是StreamSets数据收集器?StreamSets数据收集器是一个企业级,开放源码,连续大数据收集基础设施。 它有一个先进且容易使用的用户界面,使数据...
Laravel开发-stats-collector 使用Laravel轻松将统计信息发送到StatsD
Laravel开发-collector-snds 用于处理来自Microsoft SND的通知的收集器加载项
2、浏览网页如果乱码,请取消使用流浏览,IE5.0版本不支持MHT文件格式请使用IE5.5或以上版本。 3、最小化可以双击右下角的图标来显示主窗体。 4、收集网页数据时最好先把一个数据库关联到我的最爱,这样就可以在...
BFSU Sentence Collector 1.0:用于英语教学的索引工具,内置大学英语教材语料库...该工具支持正则表达式检索,如输入as \S+ as可以检索出含有as well as、as much as等短语的例句。
信息收集工具Fastir_Collector-master.zip
Proficy Historian计算采集器使用示例(Calculation Collector)
IBM Pattern Modeling and Analysis Tool for Java Garbage Collector
前端开源库-stream-collector流收集器,如果提供回调,则将流中的数据缓冲到数组中
http://www.cs.cmu.edu/afs/cs/academic/class/15213-s00/L3/ CMU的垃圾回收实验(IN C) 1.这个实验由我主讲,我制作了PPT,包含三种思路, 2.并提供其中最重要也是最简单的扫描Stack Frame的源码。 3.此外,有整体...
Tower Collector Join the OpenCellID community and collect cell towers' locations from your area! Tower Collector gives you opportunity to contribute to OpenCellID.org and Mozilla Location Services ...
about solar collector
pinpoint-collector-1.5.2.war
maven-repository-collector-plugin-1.0-sources.jar
系统级编程的课程实验,实现内存的的自动回收管理。 这里需要声明的是,资源不是来自本人,资源来自网络。本着造福广大学生的目的。但是本人实在太菜,不知道如何设置资源分数为0,所以就设置为1. ...
event-collector.zip,事件收集器