Pluto_Rabbit's Blog

蒟蒻妹纸一枚，轻拍

【学习】网络流

Jacinth posted @ 2016年3月03日 11:20 in Lerning with tags 网络流 学习 Learning , 530 阅读

听说网络流很好玩。。。其实好久好久好久以前就写过。。。但已经不知道烂到哪个角落里去了QAQ

停课了就先看看网络流呗~~~

感觉网络流最重要的是建图哎。。。不然好像知道是网络流还是流不出来QAQ

快去膜hzwer的模板 传送门

不要问为什么所有的画风都是一个样。。。虽然每次都重新手打一遍但是。。。板子用的都是同一个啊

找到一个BZOJ网络流汇总的文件。。开始好好做题啦

BZOJ-1433&Codevs-2347

才不会说后面的Dinic都是拿这个的。。。

表示做完这题下午考试就有差不多的题好兴奋ヾ(o◕∀◕)ﾉヾ

源点向所有有床位的连边,需要床位的向汇点连边,如果i可以睡j的床,i向j'连边

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#define S 101
#define INF 0x7fffffff
using namespace std;

int T,n,x;
queue<int> que;
int tot=1,total=0,cnt,a[55],head[110],ne[50010],v[50010],w[50010],h[110],ans=0;
bool BFS()
{
	memset(h,-1,sizeof(h));
	while (!que.empty()) que.pop();
	h[0]=0; que.push(0);
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=ne[i])
		if (w[i]&&h[v[i]]<0)
		{
			h[v[i]]=h[now]+1; que.push(v[i]);
		}
	}
	if (h[S]==-1) return 0; else return 1;
}
int DFS(int xx,int ff)
{
	int tmp,vis=0;
	if (xx==S) return ff;
	for (int i=head[xx];i;i=ne[i])
	{
		if (w[i]&&h[v[i]]==h[xx]+1)
		{
			tmp=ff-vis;
			tmp=DFS(v[i],min(tmp,w[i]));
			w[i]-=tmp;
			w[i^1]+=tmp;
			vis+=tmp;
			if (vis==ff) return ff;
		}
	}
	if (!vis) h[xx]=-1;
	return vis;
}
void Build(int xx,int yy,int zz)
{
	ne[++tot]=head[xx]; head[xx]=tot; v[tot]=yy; w[tot]=zz;
}
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		tot=1,total=ans=0; memset(h,0,sizeof(h));
		memset(head,0,sizeof(head)),memset(v,0,sizeof(v)),memset(w,0,sizeof(w));
		scanf("%d",&n);
		for (int i=1;i<=n;++i) 
		{
			scanf("%d",&a[i]); if (a[i])  Build(i+n,S,1),Build(S,i+n,0);
		}
		for (int i=1;i<=n;++i)
		{
			scanf("%d",&x);
			if ((a[i]&&!x) || !a[i]) Build(0,i,1),Build(i,0,0),total++;
		}
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
			{
				scanf("%d",&x);
				if (x || i==j) Build(i,j+n,1),Build(j+n,i,0);
			}
		while(BFS()) ans+=DFS(0,INF);
		if (ans==total) puts("^_^"); else puts("T_T");
	}
	return 0;
}

BZOJ-3996

对，这就是楼上说的那道考试时候做的题~~~

化简结果是这样滴~~

建立S,T; S 连(i,j)边，边权为b[i,j],(i,j)连i,j边，边权为inf，i向T连边，边权为c[i]

答案是sum(b[i][j])-最小割

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
#define NN 300010
using namespace std;
struct REC
{	int ne,v,w; }e[NN*10];
int x,T,S,k,ans,h[NN],head[NN],tot,n;
queue <int> que;
void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0;
}
bool BFS()
{
	memset(h,-1,sizeof(h));
	while (!que.empty()) que.pop();
	que.push(0),h[0]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
		{	h[e[i].v]=h[now]+1; que.push(e[i].v);
			if (e[i].v==T) return 1; }
	}
	if (h[T]==-1)  return 0; else return 1;
}
int DFS(int xx,int f)
{
	int tmp,vis=f;
	if (xx==T) return f;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		tmp=DFS(e[i].v,min(f,e[i].w));
		e[i].w-=tmp,e[i^1].w+=tmp,vis-=tmp;
		if (!vis) return f;
	}
	if (vis==f) h[xx]=-1;
	return f-vis;
}
int main()
{
	scanf("%d",&n); T=n*n+n+1,S=0,k=n,tot=1;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
		{
			scanf("%d",&x); ans+=x;
			Build(S,++k,x);	Build(k,i,INF);	Build(k,j,INF);
		}
	for (int i=1;i<=n;++i) scanf("%d",&x),Build(i,T,x);
	while (BFS()) ans-=DFS(0,INF);
	printf("%d\n",ans);
	return 0;
}

BZOJ-1143&BZOJ-2718

最长反链=最小路径覆盖。。。floyd传递闭包后，用n-二分图最大匹配数即为答案，二分图最大匹配数用网络流你咬我啊~~

2718是权限题。。。本宝宝没有权限号。。只能口胡了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring> 
#include <queue>
#define INF 0x3f3f3f3f
#define NN 405
#define MM 50005
using namespace std;

int h[NN],head[NN],cur[NN],T,S=0,x,y,a[NN][NN],ans,tot=1,n,m;
struct REC
{
	int ne,v,w;
}e[MM];

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0;
}

bool BFS()
{
	queue<int>que;
	memset(h,-1,sizeof(h));
	que.push(0); h[0]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]==-1)
		{	h[e[i].v]=h[now]+1;	que.push(e[i].v);	}
	}
	if (h[T]==-1) return 0;else return 1;
}

int dfs(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=cur[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=dfs(e[i].v,min(ff-vis,e[i].w));
		e[i].w-=tmp,e[i^1].w+=tmp;
		if (e[i].w)cur[xx]=i; vis+=tmp;
		if (vis==ff) return vis;
	}
	if (!vis) h[xx]=-1;
	return vis;
}
int main()
{
	scanf("%d%d",&n,&m); T=2*n+1;
	for (int i=1;i<=m;++i) scanf("%d%d",&x,&y),a[x][y]=1;
	for (int k=1;k<=n;++k)
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
			if (a[i][k] && a[k][j]) a[i][j]=1;
	for (int i=1;i<=n;++i) Build(0,i,1),Build(i+n,T,1);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			if (a[i][j]) Build(i,j+n,INF);
	while (BFS()) {	memcpy(cur,head,sizeof(head));	ans+=dfs(0,INF);}
	printf("%d\n",n-ans);
	return 0;
}

BZOJ-2768&BZOJ-1934

这两题一模一样的辣。。。所有赞成的连源点，反对的连汇点，然后是朋友的相互连，跑啊跑就跑粗来惹(￣︶￣)↗

#include <cstdio> 
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define S 0
#define T 501
using namespace std;

template <int NN,int MM>
struct ISAP
{
	int head[NN],d[NN],gap[NN],cur[NN],pre[NN],tot;
	struct Edge
	{
		int v,ne,w,f;
	}e[MM];
	void cl(){	tot=1; memset(head,0,sizeof(head));	}
	void build(int xx,int yy,int zz)
	{
		e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz,e[tot].f=0;
		e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0,e[tot].f=0;
	}
	void BFS(int tt)
	{
		queue<int>que;
		que.push(tt);
		memset(d,-1,sizeof(d)); memset(gap,0,sizeof(gap));
		d[tt]=0;
		while (!que.empty())
		{
			int now=que.front(); que.pop();
			++gap[d[now]];
			for (int i=head[now];i;i=e[i].ne)
			if (d[e[i].v]==-1)
			{	d[e[i].v]=d[now]+1;	que.push(e[i].v);}
		}
	}
	int isap(int ss,int tt,int num)
	{
		BFS(tt);
		
		int ans=0,u=ss,flow=INF;
		memcpy(cur,head,sizeof(head));
		while (d[ss]<num)
		{
			int &i=cur[u];
			for (;i;i=e[i].ne)
			if (e[i].w>e[i].f && d[u]==d[e[i].v]+1)
			{
				u=e[i].v;
				pre[e[i].v]=i;
				flow=min(flow,e[i].w-e[i].f);
				if (u==tt)
				{
					while(u!=ss)
					{
						e[pre[u]].f+=flow;
						e[pre[u]^1].f-=flow;
						u=e[pre[u]^1].v;
					}
					ans+=flow; flow=INF;
				}
				break;
			}
			if (i==0)
			{
				if (--gap[d[u]]==0) break;
				int dmin=num-1;
				cur[u]=head[u];
				for (int j=head[u];j;j=e[j].ne)
				if (e[j].w>e[j].f) dmin=min(dmin,d[e[j].v]);
				d[u]=dmin+1,++gap[d[u]];
				if (u!=ss) u=e[pre[u]^1].v;
			}
		}
		return ans;
	}
};
ISAP<1000,1000000> Sap;
int n,m,x,y;
int main()
{
	scanf("%d%d",&n,&m);
	Sap.cl();
	for (int i=1;i<=n;++i) 
	{
		scanf("%d",&x); 
		Sap.build(S,i,x); Sap.build(i,T,x^1);
	}
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		Sap.build(x,y,1);
		Sap.build(y,x,1);
	}
	printf("%d\n",Sap.isap(S,T,Sap.tot));
	return 0;
}

BZOJ-3504

如果只能走2次就连一条流量为2的边，如果随便走就连INF的边。起点连源点，终点连汇点。。

不过防止a1走b2的作死就把b1,b2倒一倒再跑一遍，两次都过就可以啦~\(≧▽≦)/~

#include <cstdio> 
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define S 0
#define T 51
using namespace std;

template <int NN,int MM>
struct ISAP
{
	int head[NN],d[NN],gap[NN],cur[NN],pre[NN],tot;
	struct Edge
	{
		int v,ne,w,f;
	}e[MM];
	void cl(){	tot=1; memset(head,0,sizeof(head));	}
	void build(int xx,int yy,int zz)
	{
		e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz,e[tot].f=0;
		e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0,e[tot].f=0;
	}
	void BFS(int tt)
	{
		queue<int>que;
		que.push(tt);
		memset(d,-1,sizeof(d)); memset(gap,0,sizeof(gap));
		d[tt]=0;
		while (!que.empty())
		{
			int now=que.front(); que.pop();
			++gap[d[now]];
			for (int i=head[now];i;i=e[i].ne)
			if (d[e[i].v]==-1)
			{	d[e[i].v]=d[now]+1;	que.push(e[i].v);}
		}
	}
	int isap(int ss,int tt,int num)
	{
		BFS(tt);
		
		int ans=0,u=ss,flow=INF;
		memcpy(cur,head,sizeof(head));
		while (d[ss]<num)
		{
			int &i=cur[u];
			for (;i;i=e[i].ne)
			if (e[i].w>e[i].f && d[u]==d[e[i].v]+1)
			{
				u=e[i].v;
				pre[e[i].v]=i;
				flow=min(flow,e[i].w-e[i].f);
				if (u==tt)
				{
					while(u!=ss)
					{
						e[pre[u]].f+=flow;
						e[pre[u]^1].f-=flow;
						u=e[pre[u]^1].v;
					}
					ans+=flow; flow=INF;
				}
				break;
			}
			if (i==0)
			{
				if (--gap[d[u]]==0) break;
				int dmin=num-1;
				cur[u]=head[u];
				for (int j=head[u];j;j=e[j].ne)
				if (e[j].w>e[j].f) dmin=min(dmin,d[e[j].v]);
				d[u]=dmin+1,++gap[d[u]];
				if (u!=ss) u=e[pre[u]^1].v;
			}
		}
		return ans;
	}
};
ISAP<1000,1000000> Sap;

int n,a1,a2,an,b1,b2,bn,a[55][55];

int main()
{
	while (scanf("%d%d%d%d%d%d%d",&n,&a1,&a2,&an,&b1,&b2,&bn)!=EOF)
	{
		a1++,a2++,b1++,b2++;
		memset(a,0,sizeof(a));
		for (int i=1;i<=n;++i)
		{
			char ch[55];
			scanf("%s",ch);
			for (int j=1;j<=n;++j)
				if (ch[j-1]=='O') a[i][j]=1;
				else if (ch[j-1]=='N') a[i][j]=2;
		}
		//for (int i=1;i<=n;++i) for (int j=1;j<=n;++j) printf("%d ",a[i][j]);
		Sap.cl();
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (a[i][j]==1) Sap.build(i,j,2);
				else if (a[i][j]==2) Sap.build(i,j,INF);
		Sap.build(S,a1,an*2); Sap.build(S,b1,bn*2);
		Sap.build(a2,T,an*2); Sap.build(b2,T,bn*2);
		if (Sap.isap(S,T,Sap.tot)<(an+bn)*2)	{	puts("No"); continue;}
		
		Sap.cl();
		for (int i=1;i<=n;++i)
			for (int j=1;j<=n;++j)
				if (a[i][j]==1) Sap.build(i,j,2);
				else if (a[i][j]==2) Sap.build(i,j,INF);
		Sap.build(S,a1,an*2); Sap.build(S,b2,bn*2);
		Sap.build(a2,T,an*2); Sap.build(b1,T,bn*2);
		if (Sap.isap(S,T,Sap.tot)<(an+bn)*2) { puts("No"); continue;}
		puts("Yes");
	}
	return 0;
}

BZOJ-1001

QAQ我才不会说窝连bzoj1000都没做呢╮(╯_╰)╭

感觉题目写得好明显的了呢~~
不过源点是1，汇点是n*m，憋搞错就可以咯

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 1000010
using namespace std;

int tot=1,n,m,S=1,T,x,head[NN],h[NN],ans=0;
struct REC
{
	int ne,v,w;
}e[NN<<3];

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=zz;
}

bool BFS()
{
	queue<int> que; memset(h,-1,sizeof(h));
	que.push(S); h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
		{
			h[e[i].v]=h[now]+1; que.push(e[i].v);
		}
	}
	return h[T]!=-1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (h[e[i].v]==h[xx]+1 && e[i].w)
	{
		int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
		e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}

int main()
{
	scanf("%d%d",&n,&m); T=n*m;
	for (int i=1;i<=n;++i)
		for (int j=1;j<m;++j)
			scanf("%d",&x),Build((i-1)*m+j,(i-1)*m+j+1,x);
	for (int i=1;i<n;++i)
		for (int j=1;j<=m;++j)
			scanf("%d",&x),Build((i-1)*m+j,i*m+j,x);
	for (int i=1;i<n;++i)
		for (int j=1;j<m;++j)
			scanf("%d",&x),Build((i-1)*m+j,i*m+j+1,x);
	while (BFS()) ans+=DFS(1,INF);
	printf("%d\n",ans);
	return 0;
}

BZOJ-1497

对于消费和盈利的点建立二分图，开始答案为所有的盈利和，然后从源点向消费点连边，流量为消费值，盈利点向汇点连边，流量为盈利值中间盈利对应的消费连边，流量为INF，用开始的答案减去最小割就是答案

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 100100
#define MM 1000010
using namespace std;

int head[NN],h[NN],x,y,z,n,m,ans=0,tot=1,S=0,T;
struct REC
{
	int ne,v,w;
}e[MM];

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0;
}

bool BFS()
{
	queue<int>que; memset(h,-1,sizeof(h));
	que.push(S), h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
			if (e[i].w && h[e[i].v]<0)
				que.push(e[i].v), h[e[i].v]=h[now]+1;
	}
	return h[T]!=-1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]==h[xx]+1)
		{
			int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
			e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
			if (vis==ff) return ff;
		}
	if (!vis) h[xx]=-1;
	return vis;
}

int main()
{
	scanf("%d%d",&n,&m); T=n+m+1;
	memset(head,0,sizeof(head));
	for (int i=1;i<=n;++i) scanf("%d",&x),Build(i,T,x);
	for (int i=1;i<=m;++i) 
		scanf("%d%d%d",&x,&y,&z),Build(i+n,x,INF),Build(i+n,y,INF),Build(S,i+n,z),ans+=z;
	while (BFS()) ans-=DFS(S,INF);
	printf("%d\n",ans);
	return 0;
}

BZOJ-1412

源点向所有羊连无穷边，羊向狼连流量为1的边，所有狼向汇点连无穷边跑最大流

网络流写得越来越6咯

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MM 500010
#define NN 10010

int head[NN],h[NN],tot=1,n,m,a[110][110],S=0,T=10001,ans=0;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

struct REC
{
	int v,w,ne;
}e[MM];

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0;
}

bool BFS()
{
	queue<int> que; memset(h,-1,sizeof(h));
	que.push(S); h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
			h[e[i].v]=h[now]+1, que.push(e[i].v);
	}
	return h[T]!=-1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (h[e[i].v]==h[xx]+1 && e[i].w)
	{
		int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
		e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}


int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j) scanf("%d",&a[i][j]);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
		{
			if (a[i][j]==1) Build(0,(i-1)*m+j,INF);
			else if (a[i][j]==2) Build((i-1)*m+j,T,INF);
			for (int k=0;k<4;++k)
			{
				int xx=i+dx[k],yy=j+dy[k];
				if (xx<1 || yy<1 || xx>n || yy>m || a[i][j]==2) continue;
				if (a[i][j]!=1 || a[xx][yy]!=1)
					Build((i-1)*m+j,(xx-1)*m+yy,1);
			}
		}
	while (BFS()) ans+=DFS(S,INF);
	printf("%d\n",ans);
	return 0;
}

BZOJ-1066

源点向每只蜥蜴连1的边，蜥蜴向每个能到的石柱连边，石柱拆成两个点x,y，从x到y连长为石柱高度的边；如果某点能到边界，向汇点连无穷边跑最大流

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 1010
#define MM 500010
#define N 25
using namespace std;

int tot=1,ans=0,S=0,T=801,head[NN],h[NN],a[N][N],mark[N][N],n,m,d;
char ch[N];
struct REC
{
	int ne,v,w;
}e[MM];

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].w=zz;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].w=0;
}

bool BFS()
{
	queue<int> que; memset(h,-1,sizeof(h));
	que.push(S); h[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
		{
			h[e[i].v]=h[now]+1; que.push(e[i].v);
		}
	}
	return h[T]!=-1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (h[e[i].v]==h[xx]+1 && e[i].w)
	{
		int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
		e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}

bool Judge(int xa,int ya,int xb,int yb)
{
	if (((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb))<=(d*d) && a[xa][ya] && a[xb][yb]) return 1;
	else return 0;
}

int main()
{
	scanf("%d%d%d",&n,&m,&d);
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch+1);
		for (int j=1;j<=m;++j) a[i][j]=ch[j]-'0';
	}
	int tmp=0;
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) mark[i][j]=++tmp;
	for (int i=1;i<=n;++i)
	{
		scanf("%s",ch+1);
		for (int j=1;j<=m;++j)
			if (ch[j]=='L') Build(S,mark[i][j],1),++ans;
	}
	for (int i=1;i<=d;++i)
		for (int j=d+1;j<=n-d;++j)
			Build(mark[j][i]+400,T,INF),Build(mark[j][m-i+1]+400,T,INF);
	for (int i=1;i<=d;++i)
		for (int j=1;j<=m;++j)
			Build(mark[i][j]+400,T,INF),Build(mark[n-i+1][j]+400,T,INF);
	for (int xa=1;xa<=n;xa++)
		for (int ya=1;ya<=m;ya++)
			for (int xb=xa-d;xb<=xa+d;xb++)
				for (int yb=ya-d;yb<=ya+d;yb++)
					if (Judge(xa,ya,xb,yb) && (xa!=xb || ya!=yb))
						Build(mark[xa][ya]+400,mark[xb][yb],INF);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j)
			if (a[i][j]) Build(mark[i][j],mark[i][j]+400,a[i][j]);
	while (BFS()) ans-=DFS(S,INF);
	printf("%d\n",ans);
	return 0;
}

BZOJ-3158

发现两两关系只会发生在奇数特征值和偶数特征值的点之间，源点向所有偶数特征值的点连流量为价值的边，所有奇数特征值的点向汇点连流量为价值的边，所有偶数特征值的点向有冲突的奇数特征值的点连流量无穷的边，就变成最小割模型，答案为所有收益-流量

听说3275也是一样哦。。然而苯宝宝没有权限号哦

所以就这样口胡辣

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 1005
#define MM 1000005
#define LL long long
using namespace std;
 
queue <int> que;
struct REC
{
    int ne,v,w;
}e[MM];
int tot=1,n,a[NN],b[NN],head[NN],h[NN],S=0,T,ans;
void Build(int xx,int yy,int zz)
{
    e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
    e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=0;
}
bool BFS()
{
    while (!que.empty()) que.pop();
    memset(h,-1,sizeof(h));
    que.push(S), h[S]=0;
    while (!que.empty())
    {
        int now=que.front(); que.pop();
        for (int i=head[now];i;i=e[i].ne)
            if (e[i].w && h[e[i].v]<0)
                h[e[i].v]=h[now]+1, que.push(e[i].v);
    }
    if (h[T]==-1) return 0; else return 1;
}
int DFS(int xx,int ff)
{
    if (xx==T) return ff;
    int vis=0;
    for (int i=head[xx];i;i=e[i].ne)
        if (e[i].w && h[e[i].v]==h[xx]+1)
        {
            int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
            e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
            if (vis==ff) return vis;
        }
    if (!vis) h[xx]=-1;
    return vis;
}
int GCD(int a,int b)
{
    while (a)a ^= b ^= a ^= b %= a;
    return b;
}
bool Judge(int xx,int yy)
{
    LL tmp=(LL)xx*xx+(LL)yy*yy,sq=sqrt(tmp);
    if (sq*sq!=tmp) return 1;
    if (GCD(xx,yy)>1) return 1;
    return 0;
}
int main()
{
    scanf("%d",&n); T=n+1;
    for (int i=1;i<=n;++i) scanf("%d",&a[i]);
    for (int i=1;i<=n;++i) scanf("%d",&b[i]),ans+=b[i];
    for (int i=1;i<=n;++i)
        if (a[i]%2==1) Build(S,i,b[i]); else Build(i,T,b[i]);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if ((a[i]%2==1) && (a[j]%2==0))
                if (!Judge(a[i],a[j])) Build(i,j,INF);
    while (BFS()) ans-=DFS(S,INF);
    printf("%d\n",ans);
    return 0;
}

BZOJ-1305

二分答案ans，每个男孩拆成两个点ai和ai'，每个女孩拆成两个点bi和bi'，源点向每个ai连一条流量为ans的边，每个bi向汇点连一条流量为ans的边，如果男孩i喜欢女孩j，ai向bi连一条流量为1的边，否则ai'向bi'连一条流量为1的边，每个ai向ai'连一条流量为k的边，表示最多和k个不喜欢的女孩跳舞；每个bi'向bi连一条流量为k的边，如果流量=ans*n则可行，l=mid+1,否则r=mid

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 1010
#define MM 500001
using namespace std;
 
queue <int> que;
int h[NN],S=0,T=1001,tot,head[NN],n,k,l,r,ans,anss;
char ch[55];
bool mp[NN][NN]={0};
struct REC
{
    int ne,v,w;
}e[MM];
 
void Build(int xx,int yy,int zz)
{
    e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;
    e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].w=0;
}
bool BFS()
{
    while (!que.empty()) que.pop();
    memset(h,-1,sizeof(h));
    que.push(S), h[S]=0;
    while (!que.empty())
    {
        int now=que.front(); que.pop();
        for (int i=head[now];i;i=e[i].ne)
            if (e[i].w && h[e[i].v]<0)
                h[e[i].v]=h[now]+1, que.push(e[i].v);
    }
    if (h[T]==-1) return 0; else return 1;
}
 
int DFS(int xx,int ff)
{
    if (xx==T) return ff;
    int vis=0;
    for (int i=head[xx];i;i=e[i].ne)
        if (e[i].w && h[e[i].v]==h[xx]+1)
        {
            int tmp=DFS(e[i].v,min(ff-vis,e[i].w));
            e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
            if (vis==ff) return vis;
        }
    if (!vis) h[xx]=-1;
    return vis;
}
 
bool Work(int xx)
{
    memset(head,0,sizeof(head)); tot=1;
    for (int i=1;i<=n;++i) Build(S,i,xx),Build(i,i+500,k),Build(n+i+500,n+i,k),Build(n+i,T,xx);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            if (mp[i][j]) Build(i,n+j,1); else Build(i+500,n+j+500,1);
    ans=0;
    while (BFS()) ans+=DFS(S,INF);
    if (ans>=n*xx) return 1; else return 0;
}
 
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;++i)
    {
        scanf("%s",ch);
        for (int j=1;j<=n;++j)
            if (ch[j-1]=='Y') mp[i][j]=1;
    }
    l=0, r=50, anss=0;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (Work(mid)) anss=mid, l=mid+1; else r=mid-1;
    }
    printf("%d\n",anss);
    return 0;
}

BZOJ-2039

源点向每个员工连流量为收益的边，每两个员工之间连Ei,j*2的边，每个员工i再向汇点连ΣEi,j的边，得到最小割模型，答案即为sum-流量

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <algorithm>
#include <cstring>
#define INF 0x3f3f3f3f
#define LL long long
#define NN 1010
#define MM 2001000
using namespace std;
 
queue<int>que;
int n,m,S,T,head[NN],h[NN],tot=1;
LL summ,sum[NN],mp[NN][NN],a[NN];
struct Edge
{
    int v,ne; LL w;
}e[MM];
void Build(int xx,int yy,LL zz) {e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].w=zz;}
bool BFS()
{
    while (!que.empty()) que.pop();
    memset(h,-1,sizeof(h)); h[S]=0, que.push(S);
    while (!que.empty())
    {
        int now=que.front(); que.pop();
        for (int i=head[now];i;i=e[i].ne)
            if (e[i].w && h[e[i].v]<0)
                h[e[i].v]=h[now]+1, que.push(e[i].v);
    }
    return h[T]!=-1;
}
 
LL DFS(int xx,LL ff)
{
    if (xx==T) return ff;
    LL vis=0ll;
    for (int i=head[xx];i;i=e[i].ne)
        if (e[i].w && h[e[i].v]==h[xx]+1)
        {
            LL tmp=DFS(e[i].v,min(e[i].w,ff-vis));
            e[i].w-=tmp, e[i^1].w+=tmp, vis+=tmp;
            if (vis==ff) return vis;
        }
    if (!vis) h[xx]=-1;
    return vis;
}
 
int main()
{
    scanf("%d",&n); S=n+1, T=n+2;
    for (int i=1;i<=n;++i) scanf("%lld",&a[i]);
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j) scanf("%lld",&mp[i][j]),sum[i]+=mp[i][j];
    for (int i=1;i<=n;++i) Build(S,i,sum[i]), Build(i,S,0), summ+=sum[i];
    for (int i=1;i<=n;++i) Build(i,T,a[i]), Build(T,i,0);
    for (int i=1;i<=n;++i)
        for (int j=i+1;j<=n;++j) Build(i,j,mp[i][j]*2), Build(j,i,mp[i][j]*2);
    while (BFS()) summ-=DFS(S,INF);
    printf("%lld\n",summ);
    return 0;
}

BZOJ-1221

自己生日的题号哎。。。

开始做费用流咯。。。尽快把板子记下来哦

拆点，源点向每个i连一条流量无穷费用f的边表示直接买毛巾，每个i向i'连一条流量无穷费用0的边，每个i'向t连一条流量为ni费用0的边，表示需要的毛巾；每个i'向i+a连一条流量无穷费用fa的边，表示快洗；每个i'向i+b连一条流量无穷费用fb的边，表示慢洗

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
#define INF 0x3f3f3f3f
#define NN 2100
#define MM 200000
using namespace std;

int n,a,b,f,faa,fbb,dis[NN],fa[NN],tot=1,head[NN],x,S=0,T,ans;
queue<int>que;
bool vis[NN];
struct REC
{
	int ne,v,u,c,w;
}e[MM];

void Build(int xx,int yy,int zz,int cc)
{
	e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].u=xx,e[tot].w=zz,e[tot].c=cc;
	e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].u=yy,e[tot].w=0,e[tot].c=-cc;
}
bool SPFA()
{
	memset(dis,0x3f,sizeof(dis));
	while (!que.empty()) que.pop();
	que.push(S), dis[S]=0;
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && dis[e[i].v]>dis[now]+e[i].c)
		{
			dis[e[i].v]=dis[now]+e[i].c;
			fa[e[i].v]=i;
			if (!vis[e[i].v])
			{
				vis[e[i].v]=1; que.push(e[i].v);
			}
		}
		vis[now]=0;
	}
	if (dis[T]==INF) return 0; else return 1;
}

void MCF()
{
	int xx=INF;
	for (int i=fa[T];i;i=fa[e[i].u]) xx=min(e[i].w,xx);
	for (int i=fa[T];i;i=fa[e[i].u]) e[i].w-=xx, e[i^1].w+=xx, ans+=xx*e[i].c;
}

int main()
{
	scanf("%d%d%d%d%d%d",&n,&a,&b,&f,&faa,&fbb); T=n*2+1;
	for (int i=1;i<=n;++i) 
	{
		scanf("%d",&x), Build(S,i+n,INF,f), Build(S,i,x,0), Build(i+n,T,x,0);
		if (i<n) Build(i,i+1,INF,0);
		if (i+a+1<=n) Build(i,i+n+a+1,INF,faa);
		if (i+b+1<=n) Build(i,i+n+b+1,INF,fbb);
	}
	while (SPFA()) MCF();
	printf("%d\n",ans);
	return 0;
}

BZOJ-2424

当然也是一道费用流的题啊QAQ

拆点，源点向i连一条流量无穷，费用di的边，表示订货，i向i'连一条流量无穷费用为0的边，所有i'向汇点连流量ui费用0的边表示卖出，所有i向i+1连一条流量S费用m的边表示存储费用，然后跑费用流

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define INF 0x3f3f3f3f
#define NN 2005
#define MM 1000010
#define LL long long
using namespace std;
queue<int>que;
 
int tot=1,dis[NN],head[NN],fa[NN],n,m,s,x,S=0,T=2001;
LL ans;
bool vis[NN];
struct Edge
{
    int ne,u,v,w,c;
}e[MM];
void Build(int xx,int yy,int zz,int cc)
{
    e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx, e[tot].w=zz, e[tot].c=cc;
    e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy, e[tot].w=0, e[tot].c=-cc;
}
bool SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    while (!que.empty()) que.pop();
    que.push(S), dis[S]=0; vis[S]=1;
    while (!que.empty())
    {
        int now=que.front(); que.pop();
        for (int i=head[now];i;i=e[i].ne)
        if (e[i].w && dis[e[i].v]>dis[now]+e[i].c)
        {
            dis[e[i].v]=dis[now]+e[i].c;
            fa[e[i].v]=i;
            if (!vis[e[i].v]) vis[e[i].v]=1, que.push(e[i].v);
        }
        vis[now]=0;
    }
    if (dis[T]==INF) return 0; else return 1;
}
 
void MCF()
{
    int xx=INF;
    for (int i=fa[T];i;i=fa[e[i].u]) xx=min(xx,e[i].w);
    for (int i=fa[T];i;i=fa[e[i].u]) e[i].w-=xx, e[i^1].w+=xx, ans+=(LL)xx*e[i].c;
}
 
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for (int i=1;i<=n;++i) scanf("%d",&x), Build(i,T,x,0);
    for (int i=1;i<=n;++i) scanf("%d",&x), Build(S,i,INF,x);
    for (int i=1;i<=n;++i) Build(i,i+1,s,m);
    while (SPFA()) MCF();
    printf("%lld",ans);
    return 0;
}

BZOJ-2245

源点向每类产品连流量为Ci的边，每类产品向能生产该产品的员工连无穷边，每个员工在每一段上向汇点连t[i]-t[i-1]流量w[i]费用的边，跑费用流即可

#include <iostream> 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstdlib>
#define INF 0x3f3f3f3f
#define LL long long
#define NN 255
#define MM 500010
#define SS 11
#define N 1005
using namespace std;
queue<int>que;
int dis[N],head[N],c[NN],s[NN],t[NN][SS],w[NN][SS],fa[N],a[NN][NN],n,m,T=1001,S=0,tot=1;
LL ans=0;
bool vis[N];
struct Edge
{
    int ne,u,v,w,c;
}e[MM];
void Build(int xx,int yy,int zz,int cc)
{
    e[++tot].ne=head[xx], head[xx]=tot, e[tot].v=yy, e[tot].u=xx, e[tot].w=zz, e[tot].c=cc;
    e[++tot].ne=head[yy], head[yy]=tot, e[tot].v=xx, e[tot].u=yy, e[tot].w=0, e[tot].c=-cc;
}
bool SPFA()
{
    memset(dis,0x3f,sizeof(dis));
    while (!que.empty()) que.pop();
    dis[S]=0, vis[S]=1, que.push(S);
    while (!que.empty())
    {
        int now=que.front(); que.pop();
        for (int i=head[now];i;i=e[i].ne)
        if (e[i].w && dis[e[i].v]>dis[now]+e[i].c)
        {
            dis[e[i].v]=dis[now]+e[i].c;
            fa[e[i].v]=i;
            if (!vis[e[i].v]) vis[e[i].v]=1, que.push(e[i].v);
        }
        vis[now]=0;
    }
    if (dis[T]==INF) return 0; else return 1;
}
 
void MCF()
{
    int xx=INF;
    for (int i=fa[T];i;i=fa[e[i].u]) xx=min(xx,e[i].w);
    for (int i=fa[T];i;i=fa[e[i].u]) e[i].w-=xx, e[i^1].w+=xx, ans+=(LL)e[i].c*xx;
}
 
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;++i) scanf("%d",&c[i]);
    for (int i=1;i<=m;++i)
        for (int j=1;j<=n;++j) scanf("%d",&a[i][j]);
    for (int i=1;i<=m;++i)
    {
        scanf("%d",&s[i]);
        for (int j=1;j<=s[i];++j) scanf("%d",&t[i][j]);
        t[i][s[i]+1]=INF;
        for (int j=1;j<=s[i]+1;++j) scanf("%d",&w[i][j]);
    }
    for (int i=1;i<=n;++i) Build(S,i,c[i],0);
    for (int i=1;i<=m;++i)
        for (int j=1;j<=n;++j)
            if (a[i][j]) Build(j,i+n,INF,0);
    for (int i=1;i<=m;++i)
        for (int j=1;j<=s[i]+1;++j) Build(i+n,T,t[i][j]-t[i][j-1],w[i][j]);
    while (SPFA()) MCF();
    printf("%lld",ans);
    return 0;
}

萌萌哒分割线==========

听说有网络流24题。。。

太空飞行计划问题

#include <iostream> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define NN 301
#define MM 200010
#define INF 0x7fffffff
using namespace std;

struct REC
{
	int ne,w,v;
}e[MM];
int m,n,ans,sum,x,head[NN],tot=1,h[NN],T,S=0;

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx]; head[xx]=tot; e[tot].v=yy; e[tot].w=zz;
	e[++tot].ne=head[yy]; head[yy]=tot; e[tot].v=xx; e[tot].w=0;
}

bool BFS()
{
	queue <int> que;
	memset(h,-1,sizeof(h)); h[0]=0;
	que.push(0);
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
		{
			h[e[i].v]=h[now]+1;
			que.push(e[i].v);
		}
	}
	if (h[T]==-1) return 0; else return 1;
}

int DFS(int xx,int ff)
{
	int vis=0;
	if (xx==T) return ff;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=ff-vis;
		tmp=DFS(e[i].v,min(tmp,e[i].w));
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}

int main()
{
	scanf("%d%d",&m,&n); T=n+m+1;
	for (int i=1;i<=m;++i)
	{
		scanf("%d",&x),sum+=x;
		Build(S,i,x);
		while (getchar()!='\n')
		{
			scanf("%d",&x);
			Build(i,x+m,INF);
		}
	}
	for (int i=1;i<=n;++i)
		scanf("%d",&x),Build(i+m,T,x);
	while (BFS()) ans+=DFS(0,INF);
	printf("%d\n",sum-ans);
	return 0;
}

最小路径覆盖问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define INF 0x7fffffff
#define NN 210
#define MM 400010
using namespace std;

struct REC
{
	int v,ne,w;
}e[MM];
int head[NN<<2],n,m,x,y,S,T,h[NN<<2],tot=1,ans;
void Build(int xx,int yy,int zz)
{
	e[++tot].v=yy; e[tot].ne=head[xx]; head[xx]=tot; e[tot].w=zz;
	e[++tot].v=xx; e[tot].ne=head[yy]; head[yy]=tot; e[tot].w=0;
}

bool BFS()
{
	memset(h,-1,sizeof(h)); h[0]=0;
	queue <int> que;
	que.push(0);
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w && h[e[i].v]<0)
		{
			h[e[i].v]=h[now]+1;
			que.push(e[i].v);
		}
	}
	if (h[T]==-1) return 0; else return 1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=ff-vis;
		tmp=DFS(e[i].v,min(e[i].w,tmp));
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}

int main()
{
	scanf("%d%d",&n,&m);
	S=0,T=n*2+1;
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		Build(x,y+n,INF);
	}
	for (int i=1;i<=n;++i) Build(S,i,1),Build(i+n,T,1);
	ans=n;
	while (BFS()) ans-=DFS(0,INF);
	printf("%d\n",ans);
	return 0;
}

魔术球问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#define NN 10010
#define MM 200010
#define INF 0x7fffffff
using namespace std;

int n,m=0,ans=0,head[NN],h[NN],tot=1,S=0,T=NN-10;
struct REC
{
	int ne,v,w;
}e[MM];

bool BFS()
{
	queue<int> que;
	memset(h,-1,sizeof(h)); h[0]=0;
	que.push(0);
	while (!que.empty())
	{
		int now=que.front(); que.pop();
		for (int i=head[now];i;i=e[i].ne)
		if (e[i].w&&h[e[i].v]<0)
		{
			h[e[i].v]=h[now]+1;
			que.push(e[i].v);
		}
	}
	if (h[T]==-1) return 0;else return 1;
}

int DFS(int xx,int ff)
{
	if (xx==T) return ff;
	int vis=0;
	for (int i=head[xx];i;i=e[i].ne)
	if (e[i].w && h[e[i].v]==h[xx]+1)
	{
		int tmp=ff-vis;
		tmp=DFS(e[i].v,min(e[i].w,tmp));
		e[i].w-=tmp;
		e[i^1].w+=tmp;
		vis+=tmp;
		if (vis==ff) return ff;
	}
	if (!vis) h[xx]=-1;
	return vis;
}

void Build(int xx,int yy,int zz)
{
	e[++tot].ne=head[xx]; head[xx]=tot; e[tot].v=yy; e[tot].w=zz;
	e[++tot].ne=head[yy]; head[yy]=tot; e[tot].v=xx; e[tot].w=0;
}

int main()
{
	scanf("%d",&n);
	while (1)
	{
		m++,ans++;
		for (int i=1;i<m;++i)
		if (sqrt(i+m)==(int)sqrt(i+m)) Build(i,m+5000,1);
		Build(S,m,1); Build(m+5000,T,1);
		while (BFS()) ans-=DFS(0,INF);
		if (ans>n)
		{
			printf("%d\n",m-1); return 0;
		}
	}
	return 0;
}

圆桌问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;
int x,n,m,S,T;
template <int NN,int MM>
struct ISAP
{
	int head[NN],d[NN],gap[NN],cur[NN],pre[NN],tot;
	struct Edge
	{
		int ne,v,w,f;
	}e[MM];
        void cl()
	{
		tot=1; memset(e,0,sizeof(e)); memset(head,0,sizeof(head));
	}
	void build(int xx,int yy,int zz)
	{
		e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].f=0,e[tot].w=zz;
		e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].f=0,e[tot].w=0;
	}
	void bfs(int tt)
	{
		queue<int>que;
		que.push(tt);
		memset(d,-1,sizeof(d));
		memset(gap,0,sizeof(gap));
		d[tt]=0;
		while (!que.empty())
		{
			int now=que.front(); que.pop();
			++gap[d[now]];
			for (int i=head[now];i;i=e[i].ne)
			if (d[e[i].v]==-1)
			{
				d[e[i].v]=d[now]+1;
				que.push(e[i].v);
			}
		}
	}
	int isap(int ss,int tt,int num)
	{
		bfs(tt);
		int ans=0,u=ss,flow=INF;
		memcpy(cur,head,sizeof(head));
		while (d[ss]<num)
		{
			int &i=cur[u];
			for (;i;i=e[i].ne)
			if (e[i].w>e[i].f && d[u]==d[e[i].v]+1)
			{
				u=e[i].v;
				pre[e[i].v]=i;
				flow=min(flow,e[i].w-e[i].f);
				if (u==tt)
				{
					while (u!=ss)
					{
						e[pre[u]].f+=flow;
						e[pre[u]^1].f-=flow;
						u=e[pre[u]^1].v;
					}
					ans+=flow; flow=INF;
				}
				break;
			}
			if (i==0)
			{
				if (--gap[d[u]]==0) break;
				int minn=num-1;
				cur[u]=head[u];
				for (int j=head[u];j;j=e[j].ne)
					if (e[j].w>e[j].f) minn=min(minn,d[e[j].v]);
				d[u]=minn+1; ++gap[d[u]];
				if (u!=ss) u=e[pre[u]^1].v;
			}
		}
		return ans;
	}
};
ISAP<1000, 1000000> Sap;

int main()
{
	scanf("%d%d",&m,&n); S=0,T=n+m+1; Sap.cl();
	for (int i=1;i<=m;++i) scanf("%d",&x),Sap.build(S,i,x);
	for (int i=1;i<=n;++i) scanf("%d",&x),Sap.build(i+m,T,x);
	for (int i=1;i<=m;++i)
		for (int j=1;j<=n;++j) Sap.build(i,j+m,1);
	printf("%d\n",Sap.isap(S,T,Sap.tot));
	return 0;
}

最长递增子序列问题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
#define INF 0x3f3f3f3f
using namespace std;

template <int NN,int MM>
struct ISAP
{
	int head[NN],d[NN],gap[NN],cur[NN],pre[NN],tot=1;
	struct Edge
	{
		int ne,v,w,f;
	}e[MM];
	void cl()
	{
		tot=1; memset(e,0,sizeof(e)); memset(head,0,sizeof(head));
	}
	void build(int xx,int yy,int zz)
	{
		e[++tot].ne=head[xx],head[xx]=tot,e[tot].v=yy,e[tot].f=0,e[tot].w=zz;
		e[++tot].ne=head[yy],head[yy]=tot,e[tot].v=xx,e[tot].f=0,e[tot].w=0;
	}
	void bfs(int tt)
	{
		queue<int>que;
		que.push(tt);
		memset(d,-1,sizeof(d));
		memset(gap,0,sizeof(gap));
		d[tt]=0;
		while (!que.empty())
		{
			int now=que.front(); que.pop();
			++gap[d[now]];
			for (int i=head[now];i;i=e[i].ne)
			if (d[e[i].v]==-1)
			{
				d[e[i].v]=d[now]+1;
				que.push(e[i].v);
			}
		}
	}
	int isap(int ss,int tt,int num)
	{
		bfs(tt);
		int ans=0,u=ss,flow=INF;
		memcpy(cur,head,sizeof(head));
		while (d[ss]<num)
		{
			int &i=cur[u];
			for (;i;i=e[i].ne)
			if (e[i].w>e[i].f && d[u]==d[e[i].v]+1)
			{
				u=e[i].v;
				pre[e[i].v]=i;
				flow=min(flow,e[i].w-e[i].f);
				if (u==tt)
				{
					while (u!=ss)
					{
						e[pre[u]].f+=flow;
						e[pre[u]^1].f-=flow;
						u=e[pre[u]^1].v;
					}
					ans+=flow; flow=INF;
				}
				break;
			}
			if (i==0)
			{
				if (--gap[d[u]]==0) break;
				int minn=num-1;
				cur[u]=head[u];
				for (int j=head[u];j;j=e[j].ne)
					if (e[j].w>e[j].f) minn=min(minn,d[e[j].v]);
				d[u]=minn+1; ++gap[d[u]];
				if (u!=ss) u=e[pre[u]^1].v;
			}
		}
		return ans;
	}
};
ISAP<1000, 1000000> Sap;
int n,f[1010],a[1010],ans1,ans2,T,S;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)	scanf("%d",&a[i]);
	memset(f,0,sizeof(f)); ans1=0;
	for (int i=1;i<=n;++i)
	{
		f[i]=1;
		for (int j=1;j<i;++j) if (a[j]<a[i]) f[i]=max(f[i],f[j]+1);
		ans1=max(ans1,f[i]);
	} 
	printf("%d\n",ans1);
	T=2*n+1; S=0;
	for (int i=1;i<=n;++i) 
	{
		if (f[i]==1) Sap.build(S,i,1);
		if (f[i]==ans1) Sap.build(i+n,T,1);
		Sap.build(i,i+n,1);
	}
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
			if (a[i]<a[j] && f[i]==f[j]-1)	Sap.build(i+n,j,1);
	printf("%d\n",Sap.isap(S,T,Sap.tot));
	Sap.cl();
	for (int i=1;i<=n;++i)
	{
		int tmp=1;
		if (i==1 || i==n) tmp=INF;
		if (f[i]==1) Sap.build(S,i,tmp);
		if (f[i]==ans1) Sap.build(i+n,T,tmp);
		Sap.build(i,i+n,tmp);
	}
	for (int i=1;i<=n;++i)
		for (int j=i+1;j<=n;++j)
			if (a[i]<a[j] && f[i]==f[j]-1) Sap.build(i+n,j,1);
	ans2=Sap.isap(S,T,Sap.tot);
	if (ans2>=INF) printf("%d\n",n); else printf("%d\n",ans2);
	return 0;
}
Small_feed 评论 (1)
1
[回复]
Avatar_small
www.modelpaper2020. 说:
2023年7月07日 00:16

News coverage of current events around the nation.Our team is made up of professional writers and citizen journalists with a wide range of journalism interests who are committed about delivering education updates in the www.modelpaper2020.in public interest while maintaining transparency is a project of experienced writers who have gathered for specialised news coverage of recent events across the nation Our team is made up of professional writers and citizen journalists with a wide range of journalism


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter