HDU 3376(最小費用最大フロー)


問題を解く構想:点を分解する方法で、同じ点を2つに分解して、容量は1.これにより、各ポイントが1回しか流れないことを保証します.費用フローを書くときにタイムアウトし、queueの初期化を関数の外に書き、省の呼び出し関数のたびに初期化し、タイムアウトせずに通過します.
#include
#include
#include
#include
using namespace std;
int map[602][602];
struct node
{
	int u,v,c,w,next,id;
}s[4420000];
int head[600*600*2+5],cnt,dis[600*600*2+5],vis[600*600*2+5],pre[600*600*2+5];
const int inf=0x3f3f3f3f;
int en,st,n;
queue q;
void add(int u,int v,int c,int w)
{
	s[cnt].u=u;
	s[cnt].v=v;
	s[cnt].c=c;
	s[cnt].w=w;
	s[cnt].id=cnt;
	s[cnt].next=head[u];
	head[u]=cnt++;
	
	s[cnt].u=v;
	s[cnt].v=u;
	s[cnt].c=0;
	s[cnt].w=-w;
	s[cnt].id=cnt;
	s[cnt].next=head[v];
	head[v]=cnt++;
}
bool spfa()
{
	fill(dis,dis+n*n*2,inf);
	fill(vis,vis+n*n*2,0);
	dis[0]=0;
	while(!q.empty()) q.pop();
	q.push(0);
	while(!q.empty())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		for(int i=head[t];i!=-1;i=s[i].next)
		{
			int v=s[i].v;
			if(s[i].c>0&&dis[v]>dis[t]+s[i].w)
			{
				dis[v]=dis[t]+s[i].w;
				pre[v]=s[i].id;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(dis[en]==inf)
	return false;
	//printf("*%d
",dis[en]); return true; } void solve() { int sum=0; while(spfa()) { int min_flow=inf; for(int i=en;i!=st;i=s[pre[i]].u) { s[pre[i]].c-=1; s[pre[i]^1].c+=1; } sum+=dis[en]; } printf("%d
",-sum-map[0][0]-map[n-1][n-1]); } int main() { //freopen("t.txt","r",stdin); while(scanf("%d",&n)!=EOF) { cnt=0; memset(head,-1,sizeof(head)); int tp=n*n; for(int i=0;i