[SDOI2010星际竞速]解题报告

本文主要是介绍[SDOI2010星际竞速]解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用这道题学了最小费用最大流，明白了一些建模的思路。

我们必须要让一个合法解与一个割集的对应。拿此题来说，原命题可以转换为要让所有点进且仅进一次，至多出一次；分别限制即可。

进且仅进一次意味着开一条边容量为1而存在一条路径从源到汇使得有且仅有这条边容量为正无穷；至多出一次意味着开一条边，这条边到源点的流至多为1.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#include<cmath>
#include<iostream>
inline int in(){char c=getchar();int x=0;while(c<'0'||c>'9')c=getchar();for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';return x;
}struct ES{int cost,c,from,to;
}e[40000];
#include<vector>
int p[1602],next[40000],tot=2;
//0是源点，1601是汇点 
inline void addedge(int cost,int c,int from,int to){e[tot]=(ES){cost,c,from,to};next[tot]=p[from],p[from]=tot++;
}
int main(){freopen("starrace.in","r",stdin);freopen("starrace.out","w",stdout);int n=in(),m=in(),i,u,v;for(i=1;i<=n;++i){addedge(in(),1,0,i<<1),addedge(-e[tot-1].cost,0,i<<1,0);addedge(0,1,i<<1,1601),addedge(0,0,1601,i<<1);addedge(0,1,0,(i<<1)-1),addedge(0,0,(i<<1)-1,0);}for(i=0;i<m;++i){u=in(),v=in();if(u==v)continue;if(u>v)swap(u,v);u=(u<<1)-1,v=v<<1;addedge(in(),0x7fffffff,u,v);addedge(-e[tot-1].cost,0,v,u);}int dis[1602],q[1602],h,t,d;int path[1602];//path(i)表示更新到i的最短路的边。 int ans=0;bool flag[1602]={0};dis[0]=0;for(;;){//splaymemset(dis+1,0x7f,1601<<2);q[0]=0,flag[0]=1;;for(h=0,t=1;h!=t;){flag[q[h]]=0,d=dis[q[h]],i=p[q[h]];h=h==1601?0:h+1;for(;i;i=next[i]){if(e[i].c&&d+e[i].cost<dis[e[i].to]){dis[e[i].to]=d+e[i].cost;path[e[i].to]=i;//cout<<i<<":"<<e[i].from<<"-("<<e[i].cost<<")>"<<e[i].to<<":"<<dis[e[i].to]<<endl;if(!flag[e[i].to]){if(h==t||dis[e[i].to]<dis[q[h]]){h=h?h-1:1601;q[h]=e[i].to;}else{q[t]=e[i].to;t=t==1601?0:t+1;}flag[e[i].to]=1;}}//cout<<i<<" ";}//cout<<":("<<h<<","<<t<<"):";//for(int i=h;i!=t;i=i==1601?0:i+1)cout<<q[i]<<" ";//cout<<endl;}//cout<<"----------\n";if(dis[1601]>1E9)break;//增广for(i=1601;i;i=e[path[i]].from){//cout<<i<<"<-";--e[path[i]].c,++e[path[i]^1].c;ans+=e[path[i]].cost;}//cout<<i<<endl;}printf("%d\n",ans);
}

这篇关于[SDOI2010星际竞速]解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---