hdu 2686 & hdu 3376 (비용 흐름, 교묘 한 건축 도)

처음부터 뜯 어야 한다 고 생각 했 습 니 다. i 와 i '의 연결 용량 은 2 이 고 비용 은 행렬 의 값 입 니 다. 하지만 생각 하 니 틀 렸 습 니 다. 그러면 점 마다 두 번 갈 수 있 습 니 다. 매번 의 비용 은 똑 같 습 니 다. 한 번 은 0 이 어야 합 니 다. 그래서 두 변 을 더 해 야 합 니 다. 용량 은 모두 1 이 고 한 변 의 비용 은 0 입 니 다.그리고 왼쪽으로, 아래로, 그리고 비용 흐름 을 달 려 서 가장 큰 비용 을 구 합 니 다.....................................................
hdu 3376 데 이 터 를 크게 틀 면 됩 니 다. N = 720010

#include<stdio.h>
#include<string.h>
#include<queue>
const int N=2000;
const int inf=0x3fffffff;
using namespace std;
int dist[N],head[N],num,start,end,n,vis[N],pre[N];
struct edge
{
	int st,ed,cost,flow,next;
}e[N*10];
void addedge(int x,int y,int c,int w)
{
	e[num].st=x;e[num].ed=y;e[num].cost=c; e[num].flow=w;e[num].next=head[x];head[x]=num++;
	e[num].st=y;e[num].ed=x;e[num].cost=-c;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
int SPFA()
{
	queue<int>Q;
	int i,v,u;
	for(i=0;i<=end;i++)
	{dist[i]=-1;vis[i]=0;pre[i]=-1;}
	dist[start]=0;vis[start]=1;
	Q.push(start);
	while(!Q.empty())
	{
		u=Q.front();Q.pop();
		vis[u]=0;
		for(i=head[u];i!=-1;i=e[i].next)
		{
			v=e[i].ed;
			if(e[i].flow>0&&dist[v]<dist[u]+e[i].cost)
			{
				dist[v]=dist[u]+e[i].cost;
				pre[v]=i;
				if(vis[v]==0)
				{
					Q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	if(pre[end]==-1)
		return 0;
	return 1;
}
int Maxcost()
{
	int i,maxflow=0,minflow,maxcost=0;
	while(SPFA())
	{
		minflow=inf;
		for(i=pre[end];i!=-1;i=pre[e[i].st])
		 if(minflow>e[i].flow)
			 minflow=e[i].flow;
		 maxflow+=minflow;
		 for(i=pre[end];i!=-1;i=pre[e[i].st])
		 {
			 e[i].flow-=minflow;
			 e[i^1].flow+=minflow;
			 maxcost+=e[i].cost;
		 }
	}
	//printf("maxflow=%d
",maxflow);
	return maxcost;
}
int main()
{
	int i,j,t,x,w;
	while(scanf("%d",&n)!=-1)
	{
		t=n*n;start=0;end=t*2+1;num=0;
		memset(head,-1,sizeof(head));
		addedge(start,1,0,2);
		addedge(t+t,end,0,2);
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
			{
				scanf("%d",&w);
				x=i*n+j-n;
				addedge(x,x+t,w,1);
				addedge(x,x+t,0,1);
				if(j+1<=n)
					addedge(x+t,x+1,0,2);
				if(i+1<=n)
					addedge(x+t,x+n,0,2);
			}
			printf("%d
",Maxcost());
	}
	return 0;
}

’