[Sdoi2010 星际竞速]巧妙的费用流、有向无环图的最小权路径覆盖

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1927
【算法分析】
我感觉挺巧妙的。。。想了好一会儿。
首先注意到，每个点最终的入度都为1。
如果把最终停在这个点不再向后走，看成是向汇点连一条边的话，那么每个点的出度都为1。
然后呢？
我们相当于取N条边。这N条有向边除了和源点相连的以外，都是不重头，不重尾的。
这想到了什么？
匹配！
因为头尾可以看成二分图的两边~于是变成最小权匹配。但是由于与源点相连的可以重合，所以新增一个二分图X部的点，利用网络流给它赋予INF这么大的容量。
然后最小费用流完美解决。
【其它】1A。
Orz。。。好不容易又排第一。。。
1 24143 edward_mj 1004K 1917MS G++ 1.90K 2010-05-18 20:41:38 2 23595 nehzilrz 888K 1964MS G++ 1.68K 2010-05-16 13:54:28 3 23547 oimaster 824K 2091MS G++ 2.48K 2010-05-16 11:05:34 4 23681 gaoxin 1256K 2683MS Pascal 1.95K 2010-05-16 18:44:59 5 23196 root 868K 2714MS G++ 1.47K 2010-05-14 14:05:05 6 23813 FDhyc 1436K 2965MS Pascal 3.32K 2010-05-17 13:33:23 【CODE】
#include #include #include const int E=2000000;
const int N=1000005;
const int INF=1000000000;
struct edge{int x,y,c,w;edge *next,*op;}sp[E],*ls[N],*fa[N];
int n,m,S,T,e,cost;
int d[N],v[N],L[N];

void addedge(int x,int y,int c,int w){
e++;
sp[e].x=x; sp[e].y=y; sp[e].c=c; sp[e].w=w;
sp[e].next=ls[x]; ls[x]=&sp[e]; sp[e].op=&sp[e+1];
e++;
sp[e].x=y; sp[e].y=x; sp[e].c=0; sp[e].w=-w;
sp[e].next=ls[y]; ls[y]=&sp[e]; sp[e].op=&sp[e-1];
}

void input(){
scanf("%d%d",&n,&m);
S=n+n+2; T=S+1;
for (int i=1,x;i<=n;i++){
scanf("%d",&x);
addedge(S-1,i+n,1,x);
}
addedge(S,S-1,INF,0);
for (int i=1,x,y,w,tmp;i<=m;i++){
scanf("%d%d%d",&x,&y,&w);
if (x>y) {tmp=x;x=y;y=tmp;}
addedge(x,y+n,1,w);
}
for (int i=1;i<=n;i++){
addedge(S,i,1,0);
addedge(i+n,T,1,0);
}
}

bool spfa(){
int head=0,tail=1;
for (int i=1;i<=T;i++){
d[i]=INF;
v[i]=0;
}
d[S]=0; v[S]=1; L[1]=S;
while (head!=tail){
head++; if (head>=N) head=0;
for (edge *t=ls[L[head]];t;t=t->next)
if (t->c && d[t->x]+t->w d[t->y]=d[t->x]+t->w;
fa[t->y]=t;
if (!v[t->y]){
v[t->y]=1;
tail++; if (tail>=N) tail=0;
L[tail]=t->y;
}
}
v[L[head]]=0;
}
if (d[T]==INF) return false;
return true;
}

void change(){
int nf=INF;
for (int i=T;i!=S;i=fa[i]->x)
if (fa[i]->c nf=fa[i]->c;
cost+=nf*d[T];
for (int i=T;i!=S;i=fa[i]->x){
fa[i]->c-=nf;
fa[i]->op->c+=nf;
}
}

int main(){
input();
cost=0;
while (spfa()) change();
printf("%dn",cost);
}