大致题意:
有n种原材料,每种一件。现在给出m个组合,每个组合包含k种原材料,代表这k种材料可以加工成一个成品。求最多能加工出多少成品。
大致思路:
先把每个点拆做a和a'。连接a->a'。设容量为1。对于每k个原材料,每个点a连接他后面的那个数拆出的点b‘。k个数中的头和尾分别连接到原点和汇点上。求出最大流即可。
吐槽一句,想出构图之后,又手贱看了一下网上的题解,大都要先对所有的点排序后求网络流。就是弄不明白为什么要排序,这里没有排序的代码也ac了。有哪位大神能解释,是我的思路有问题还是他们都是互相抄的呢。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int inf=1<<30;
const int nMax=20000;
const int mMax=300000;
class node{
public:
int c,u,v,next;
};node edge[mMax];
int ne, head[nMax];
int cur[nMax], ps[nMax], dep[nMax];
void addedge(int u, int v,int w){ ////dinic邻接表加边
edge[ne].u = u;
edge[ne].v = v;
edge[ne].c = w;
edge[ne].next = head[u];
head[u] = ne ++;
edge[ne].u = v;
edge[ne].v = u;
edge[ne].c = 0;
edge[ne].next = head[v];
head[v] = ne ++;
}
int dinic(int s, int t){ // dinic
int tr, res = 0;
int i, j, k, f, r, top;
while(1){
memset(dep, -1, sizeof(dep));
for(f = dep[ps[0]=s] = 0, r = 1; f != r;)
for(i = ps[f ++], j = head[i]; j; j = edge[j].next)
if(edge[j].c && dep[k=edge[j].v] == -1){
dep[k] = dep[i] + 1;
ps[r ++] = k;
if(k == t){
f = r; break;
}
}
if(dep[t] == -1) break;
memcpy(cur, head, sizeof(cur));
i = s, top = 0;
while(1){
if(i == t){
for(tr =inf, k = 0; k < top; k ++)
if(edge[ps[k]].c < tr)
tr = edge[ps[f=k]].c;
for(k = 0; k < top; k ++){
edge[ps[k]].c -= tr;
edge[ps[k]^1].c += tr;
}
i = edge[ps[top=f]].u;
res += tr;
}
for(j = cur[i]; cur[i]; j = cur[i] =edge[cur[i]].next){
if(edge[j].c && dep[i]+1 == dep[edge[j].v]) break;
}
if(cur[i]){
ps[top ++] = cur[i];
i = edge[cur[i]].v;
}
else{
if(top == 0) break;
dep[i] = -1;
i = edge[ps[-- top]].u;
}
}
}
return res;
}
int num[20];
int main(){
int s,t,n,m,a,b,c,i,j;
while(cin>>n>>m){
ne=1;
memset(head,0,sizeof(head));
for(i=1;i<=n;i++){
addedge(i,i+n,1);
}
while(m--){
cin>>c;
for(i=0;i<c;i++){
cin>>num[i];
}
addedge(0,num[0],1);
addedge(num[c-1]+n,2*n+1,1);
for(0;i<c-1;i++){
addedge(num[i]+n,num[i+1],1);
}
}
cout<<dinic(0,2*n+1)<<endl;
}
return 0;
}
分享到:
相关推荐
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
标签"_zoj zoj__1016 max_flow zoj__1045 zoj.rar"进一步强调了主题,特别是"max_flow"标签再次表明了这两个题目与最大流问题的关联。 至于压缩包内的"ZJU",这可能是指浙江大学(Zhejiang University)的缩写,...
【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...
【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...
"图论_网络流入门题.doc"可能包含的是图论的基本概念和网络流算法的学习材料,如最大流、最小割等,这些都是解决网络调度、资源分配等问题的关键。 4. **计算几何**: "POJ 计算几何入门题目.doc"可能介绍了计算...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...
【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...
ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...
【ZOJ1003 Crashing Balloon】这个问题是一个经典的计算机科学竞赛编程题目,主要涉及动态规划(Dynamic Programming, DP)和贪心算法(Greedy Algorithm)的知识点。在这个问题中,参赛者需要编写程序来模拟气球...
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
Problem Arrangement zoj 3777
浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...
《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...
ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...
标题“ZOJ1014.zip_zoj code_zoj1004”表明这是一个与ZOJ(ZeroJudge)在线判题系统相关的代码压缩包,其中可能包含了解决ZOJ问题1004的源代码。ZOJ是面向编程爱好者和学生的一个在线编程竞赛平台,它提供了各种算法...
【标题】"zoj.zip_zoj"所对应的资源是一个与ZOJ(Zhejiang Online Judge)相关的代码集合。ZOJ是浙江大学主办的一个在线编程竞赛平台,它提供了多种算法题目供用户练习和提交代码进行评测。这个压缩包很可能包含了在...
**ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...
【ZOJ.zip】是一个压缩包,里面包含了与ZOJ(Zhejiang Online Judge)相关的ACM(International Collegiate Programming Contest)题解。ZOJ是一个在线编程竞赛平台,它为参赛者提供了一系列算法题目进行练习,以...
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路