有源汇上下界最小费用可行流。
将每个国家拆点。
源点向一个新建节点连一条上界为总人数下界为0费用为0的边。
新建节点向每个国家的入点连一条上界为正无穷下界为0费用为0的边。
每个国家的入点向出点连一条上下界均为该国家访问人数费用为0的边。
每个国家的出点向汇点连一条上界为正无穷下界为0费用为0的边。
对于国家i能到国家j，i的出点向j的入点连一条上界为正无穷下界为0费用为机票费的边。
然后对图求一边有源汇上下界最小费用可行流即可得出最小费用。
具体做法是先将所有边的下界乘费用相加，这一部分是必须的费用，然后按照“有源汇上下界可行流”建图，从超级源向超级汇跑一遍最小费用最大流，两个费用相加即为答案。
至于本题本身的建图思路，与bzoj1927星际竞速类似，下面放一份十分良心的题解。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int h[dian],nxt[bian],ver[bian],val[bian],cos[bian];
int d[dian],v[dian],with[dian],minn[dian];
int in[dian],out[dian];
int n,m,tot,aa,mf;
int S,T,SS,TT;
void add(int a,int b,int c,int d,int e){
tot++;ver[tot]=b;val[tot]=d-c;cos[tot]=e;nxt[tot]=h[a];h[a]=tot;
tot++;ver[tot]=a;val[tot]=;cos[tot]=-e;nxt[tot]=h[b];h[b]=tot;
in[b]+=c,out[a]+=c;
mf+=c*e;
}
bool tell(){
memset(v,,sizeof(v));
memset(d,0x3f,sizeof(d));
memset(with,,sizeof(with));
memset(minn,0x3f,sizeof(minn));
queue<int>q;
q.push(S);
v[S]=;
d[S]=;
while(!q.empty()){
int x=q.front();
q.pop();
v[x]=;
for(int i=h[x];i;i=nxt[i]){
int y=ver[i];
if(d[y]>d[x]+cos[i]&&val[i]){
d[y]=d[x]+cos[i];
minn[y]=min(minn[x],val[i]);
with[y]=i;
if(!v[y]){
v[y]=;
q.push(y);
}
}
}
}
if(d[T]==0x3f3f3f3f)
return false;
return true;
}
int zeng(){
for(int i=T;i!=S;i=ver[with[i]^]){
val[with[i]]-=minn[T];
val[with[i]^]+=minn[T];
}
return minn[T]*d[T];
}
int dinic_cost(){
int r=;
while(tell())
r+=zeng();
return r;
}
int main(){
memset(h,,sizeof(h));
memset(nxt,,sizeof(nxt));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
tot=,mf=;
scanf("%d%d",&n,&m);
SS=n+n+,TT=n+n+,S=n+n+,T=n+n+;
add(SS,n+n+,,m,);
for(int i=;i<=n;i++)
add(n+n+,i,,INF,);
for(int i=;i<=n;i++)
add(n+i,TT,,INF,);
for(int i=;i<=n;i++){
scanf("%d",&aa);
add(i,n+i,aa,aa,);
}
for(int i=;i<n;i++)
for(int j=;j<=n-i;j++){
scanf("%d",&aa);
if(aa!=-)
add(n+i,i+j,,INF,aa);
}
add(TT,SS,,INF,);
for(int i=;i<=TT;i++){
if(in[i]>out[i])
add(S,i,,in[i]-out[i],);
else if(out[i]>in[i])
add(i,T,,out[i]-in[i],);
}
printf("%d",mf+dinic_cost());
return ;
}
注意题意叙述不清，每个人可以从任意一个国家开始走。