差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:图论_3 [2020/07/22 12:54]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:图论_3 [2020/07/27 22:59] (当前版本)
jxm2001 ↷ 页面2020-2021:teams:legal_string:图论_3被移动至2020-2021:teams:legal_string:jxm2001:图论_3
@@ 行 33: / 行 33: @@
 最后从黑格向有冲突的白格连一条边，容量待定。
-问题转化为最小割问题，事实上图不连通等价于没有从源点到黑格，黑格经过冲突边到白格，白格再到汇点的路径。
+问题转化为最小割问题。
+事实上网络流图不连通等价于没有从源点到黑格，再经过冲突边到白格，最后到汇点的路径。
 这又等价于不会同时选择冲突的黑格和白格，即最终的目的。
@@ 行 43: / 行 45: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXS=105,MAXN=MAXS*MAXS,MAXM=6*MAXN,Inf=0x7fffffff;
 const int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
@@ 行 204: / 行 159: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=200,MAXM=3000,Inf=0x7fffffff;
 struct Edge{
@@ 行 428: / 行 336: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=305,MAXM=18005,Inf=0x7fffffff;
 struct Edge{
@@ 行 603: / 行 464: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=2e5+5,Inf=0x7fffffff;
 struct Edge{
@@ 行 780: / 行 594: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=205,MAXM=6000,Inf=0x7fffffff;
 struct Edge{
@@ 行 967: / 行 734: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=105,MAXM=6000;
 struct Edge{
@@ 行 1132: / 行 852: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1005,MAXM=2005,Inf=0x7fffffff;
 struct Edge{
@@ 行 1315: / 行 988: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1005,MAXM=5e5+5,Inf=0x7fffffff;
 struct Edge{
@@ 行 1501: / 行 1127: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=2e5+5,Inf=0x7fffffff;
 struct Edge{
@@ 行 1657: / 行 1236: @@
 </code>
 </hidden>
+====  餐巾计划问题 ====
+[[https://www.luogu.com.cn/problem/P1251|洛谷p1251]]
+=== 题意 ===
+一个餐厅第 $i$ 天需要 $r_i$ 条新餐巾，每条新餐巾用完后得到旧餐巾，一开始餐厅没有餐巾。
+买一条新餐巾费用为 $p$；快洗一条旧餐巾时间为 $m$ 天，费用为 $f$；慢洗一条旧餐巾时间为 $n$ 天，费用为 $s$。
+数据保证 $f\gt s,m\lt n$，问餐厅营业 $N$ 天的最小花费。
+=== 题解 ===
+把一天分成一天的开始和一天的结束，一天的开始需要提供 $r_i$ 条新餐巾，于是连一条容量为 $r_i$ 费用为 $0$ 的边到汇点。
+接下来考虑三种获取新餐巾的操作。首先可以买新餐巾，对应源点连一条容量为 $\inf$ 费用为 $p$ 的边到当天的开始。
+另外也可以通过清洗之前的旧餐巾获得。不妨假设如果旧餐巾洗完就会被立即使用，不然可以留到以后再洗。这样假设的目的是减少连边数量。
+于是第 $i$ 天的结束向第 $i+m$ 天的开始连一条容量为 $\inf$ 费用为 $f$ 的边，向第 $i+n$ 天的开始连一条容量为 $\inf$ 费用为 $s$ 的边。
+再考虑维护旧餐巾，旧餐巾可以通过两种方式获取。
+首先一天的结束将有 $r_i$ 条新餐巾变成旧餐巾，于是从源点连一条容量为 $r_i$ 费用为 $0$ 的边到一天的结束。
+另外旧餐巾也可以继承前一天剩下的未被清洗的旧餐巾，对应每天结束向第二天结束连一条容量为 $\inf$ 费用为 $0$ 的边。
+最后跑最小费用最大流即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5000,MAXM=15000,Inf=0x7fffffff;
+struct Edge{
+	int to,cap,w,next;
+	Edge(int to=0,int cap=0,int w=0,int next=0){
+		this->to=to;
+		this->cap=cap;
+		this->w=w;
+		this->next=next;
+	}
+}edge[MAXM<<1];
+int head[MAXN],edge_cnt;
+void Clear(){mem(head,-1);edge_cnt=0;}//边从0开始编号
+void Insert(int u,int v,int w,int c){
+	edge[edge_cnt]=Edge(v,c,w,head[u]);
+	head[u]=edge_cnt++;
+	edge[edge_cnt]=Edge(u,0,-w,head[v]);
+	head[v]=edge_cnt++;
+}
+struct Dinic{
+	int s,t;
+	int pos[MAXN],dis[MAXN];
+	bool inque[MAXN];
+	bool spfa(){
+		mem(dis,127/3);
+		queue<int>q;
+		q.push(s);
+		inque[s]=true,dis[s]=0,pos[s]=head[s];
+		while(!q.empty()){
+			int u=q.front();q.pop();
+			inque[u]=false;
+			for(int i=head[u];~i;i=edge[i].next){
+				int v=edge[i].to;
+				if(dis[u]+edge[i].w<dis[v]&&edge[i].cap){
+					dis[v]=dis[u]+edge[i].w,pos[v]=head[v];
+					if(!inque[v]){
+						q.push(v);
+						inque[v]=true;
+					}
+				}
+			}
+		}
+		return dis[t]!=dis[0];
+	}
+	int dfs(int u,int max_flow){
+		if(u==t||!max_flow)
+		return max_flow;
+		int flow=0,temp_flow;
+		inque[u]=true;
+		for(int &i=pos[u];~i;i=edge[i].next){
+			int v=edge[i].to;
+			if(!inque[v]&&dis[u]+edge[i].w==dis[v]&&(temp_flow=dfs(v,min(max_flow,edge[i].cap)))){
+				edge[i].cap-=temp_flow;
+				edge[i^1].cap+=temp_flow;
+				flow+=temp_flow;
+				max_flow-=temp_flow;
+				if(!max_flow)
+				break;
+			}
+		}
+		inque[u]=false;
+		return flow;
+	}
+	void MCMF(int s,int t,int &flow,LL &cost){
+		this->s=s;this->t=t;
+		cost=flow=0;
+		int temp_flow;
+		mem(inque,0);
+		while(spfa()){
+			temp_flow=dfs(s,Inf);
+			flow+=temp_flow;
+			cost+=1LL*temp_flow*dis[t];
+		}
+	}
+}solver;
+int a[MAXN];
+int main()
+{
+	Clear();
+	int n=read_int(),s=n<<1|1,t=s+1;
+	_rep(i,1,n)
+	a[i]=read_int();
+	int c1=read_int(),t2=read_int(),c2=read_int(),t3=read_int(),c3=read_int();
+	_rep(i,1,n){
+		Insert(s,i+n,0,a[i]);
+		Insert(i,t,0,a[i]);
+		Insert(s,i,c1,Inf);
+		if(i+t2<=n){
+			Insert(i+n,i+t2,c2,Inf);
+			if(i+t3<=n)
+			Insert(i+n,i+t3,c3,Inf);
+		}
+	}
+	_for(i,1,n)
+	Insert(i+n,i+n+1,0,Inf);
+	int flow;LL cost;
+	solver.MCMF(s,t,flow,cost);
+	enter(cost);
+	return 0;
+}
+</code>
+</hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具