K取方格数

给定矩阵从1,1到n~m设计k条线路取走格子中的数(重复经过只取一次)k条线路和的最大值是多少

技巧:

每个点拆成入点和出点实现点边的转化
通过限制费用大小和流量大小来实现被取走的次数和贡献

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N=55;
const double eps=1e-9;
const int INF=0x3f3f3f3f;
int read()
{
	int x=0,f=0,c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return f?-x:x;
}

struct Edge
{
	int to,next,w,c;
}e[N*N*8];
int head[N*N*2],cnt=1;
void _add(int a,int b,int c,int d){e[++cnt]=(Edge){b,head[a],c,d};head[a]=cnt;}
void add(int a,int b,int c,int d){ 
//printf("%d %d %d %d\n",a,b,c,d);
_add(a,b,c,d); _add(b,a,0,-d);}
int maxflow,ans,n,s,t,k;
int F(int x,int y,int z){ return (x-1)*n+y+z*n*n; }

queue q;
bool inq[N*N*2]; 
int d[N*N*2],incf[N*N*2],pre[N*N*2];
//spfa 多次拓展 但是进入队列只有一次 
bool spfa()
{
	while(q.size()) q.pop();
	memset(inq,0,sizeof inq); memset(d,0xcf,sizeof d);
	q.push(1); inq[1]=1; incf[1]=INF; d[1]=0;
	while(q.size())
	{
		int x=q.front(); q.pop(); inq[x]=0;//注意出队标记 
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(!e[i].w) continue;
			if(d[y]

K取方格数

相关

标签