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