赤裸裸的最小费用流。
CODE:
/*
AUTHOR: Su Jiao
DATE: 2010-7-26
DESCRIPTION:
山东2009年省选 晨跑
*/
#include <stdio.h>
#include <string.h>
#define oo 0x7f7f7f7f
#define MAXEDGE 1000000
#define MAXV 1000
typedef struct struct_edge* edge;
struct struct_edge{int v,c,d;edge n,b;};
struct_edge pool[MAXEDGE];
edge top;
int S,T,V;
edge adj[MAXV];
int q[MAXV];
bool inq[MAXV];
int head,tail;
edge p[MAXV];
int d[MAXV];
void add_edge(int u,int v,int c,int d)
{
top->v=v;
top->c=c;
top->d=d;
top->n=adj[u];
adj[u]=top++;
top->v=u;
top->c=0;
top->d=-d;
top->n=adj[v];
adj[v]=top++;
adj[u]->b=adj[v];
adj[v]->b=adj[u];
}
int min_cost_flow()
{
int flow=0,cost=0;
for (;;)
{
memset(d,oo,sizeof(d));
inq[q[head=tail=0]=S]=true;
d[S]=0;
p[S]=0;
while (head<=tail)
{
int u;
inq[u=q[(head++)%MAXV]]=false;
for (edge i=adj[u];i;i=i->n)
if (i->c&&d[i->v]>d[u]+i->d)
{
if (!inq[i->v])
inq[q[(++tail)%MAXV]=i->v]=true;
d[i->v]=d[u]+i->d;
p[i->v]=i;
}
}
if (d[T]==oo) break;
else
{
int delta=oo;
for (edge i=p[T];i;i=p[i->b->v])
if (delta>i->c) delta=i->c;
for (edge i=p[T];i;i=p[i->b->v])
i->c-=delta,i->b->c+=delta;
flow+=delta;
cost+=d[T]*delta;
}
}
printf(“%d %d\n”,flow,cost);
}
int N,M;
int a,b,c;
int main()
{
scanf(“%d%d”,&N,&M);
top=pool;
S=1,T=N*2,V=N*2;
for (int i=0;i<M;i++)
scanf(“%d%d%d”,&a,&b,&c),add_edge(a+N,b,1,c);
add_edge(1,1+N,oo,0);
for (int i=2;i<N;i++) add_edge(i,i+N,1,0);
add_edge(N,N+N,oo,0);
min_cost_flow();
}