bzoj 1927: [Sdoi2010]星际竞速
题目链接
题解
可以考虑最小路径覆盖
转化成二分图之后进行最小费用最大流，把点拆违(x,x^{'})对于连向的边连到(x')上，对于连出点(u)只能经过u一次,流量为1,花费为cost[u->v]，(S->x,x'->T)
也可进行无源汇上下界网络流
拆点限制最小流量下线为1，建一条流量为1的边，比上一种方法多2n条边，但是，快一些(来自某dalao测试)
此处只给出第一种解法code
代码
/**************************************************************
Problem: 1927
User: 11101001
Language: C++
Result: Accepted
Time:3572 ms
Memory:2648 kb
****************************************************************/
// luogu-judger-enable-o2
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::max;
using std::min;
using std::queue;
const int maxm = 85007;
const int maxn = 8007;
int n,m,S=0,T;
inline int read() {
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
return x;
}
struct Edge {
int u,v,next,flow,cost;
}edge[maxm];
int a[maxn];
int num=1,head[maxn];
void add_edge(int u,int v,int flow,int cost) {
edge[++num].u=u,edge[num].v=v,edge[num].flow=flow;edge[num].cost = cost;edge[num].next = head[u];head[u]=num;
edge[++num].u=v;edge[num].v=u;edge[num].flow=0,edge[num].cost= -cost;edge[num].next = head[v];head[v]=num;
}
int dis[maxn],pre[maxn];bool vis[maxn];
bool spfa() {
memset(dis,0x3f,sizeof dis);
vis[S]=1;dis[S]=0;
queue<int>que;
que.push(S);
while(!que.empty()) {
int u=que.front();
que.pop();
for(int i=head[u];i;i=edge[i].next) {
int v=edge[i].v;
if(edge[i].flow&&dis[u]+edge[i].cost<dis[v]) {
dis[v]=edge[i].cost+dis[u];
pre[v]=i;
if(!vis[v])
que.push(v),vis[v]=1;
}
}
vis[u]=0;
}
if(dis[T]!=0x3f3f3f3f)return true;
else return false;
}
int calc() {
int ret=0;
int maxx = 0x3f3f3f3f;
for(int i=T;i!=S;i=edge[pre[i]].u)
maxx=min(edge[pre[i]].flow,maxx);
for(int i=T;i!=S;i=edge[pre[i]].u) {
edge[pre[i]].flow-=maxx;
edge[pre[i]^1].flow+=maxx;
ret+=maxx*edge[pre[i]].cost;
}
return ret;
}
int ans=0;
void HowToMakeName() {
while(spfa())
ans+=calc();
}
int main() {
n=read(),m=read();T=n<<1|1;
for(int cost,i=1;i<=n;++i) {
cost=read(),
add_edge(S,n+i,1,cost);
add_edge(S,i,1,0);
add_edge(n+i,T,1,0);
}
for(int a,b,c,i=1;i<=m;++i) {
a=read(),b=read(),c=read();
if(a>b)std::swap(a,b);
add_edge(a,b+n,1,c);
}
HowToMakeName();
printf("%d
",ans);
return 0;
}