某个国家必须经过vi次，
可以转化为上下界都为vi的边
对这张图做有源汇上下界可行最小费用流
按无源汇上下界可行流建好图，跑超级源点到超级汇点的最小费用最大流即可
#include#include #include #include using namespace std; #define N 205#define M 10500 const int inf=1e9; int src,decc;int S,T; int tot=1;int front[N],to[M<<1],nxt[M<<1],cap[M<<1],val[M<<1],from[M<<1]; int cost; int dis[N];bool vis[N]; void read(int &x){ x=0; int f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-') f=-1; c=getchar(); } while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); } x*=f;} void add(int u,int v,int w,int f){ to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; cap[tot]=w; val[tot]=f; to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; cap[tot]=0; val[tot]=-f; } int agument(int now,int flow){ vis[now]=true; if(now==T) { cost-=dis[S]*flow; return flow; } int delta; for(int i=front[now];i;i=nxt[i]) { if(cap[i] && !vis[to[i]] && dis[to[i]]==dis[now]+val[i]) { delta=agument(to[i],min(flow,cap[i])); if(delta) { cap[i]-=delta; cap[i^1]+=delta; return delta; } } } return 0;} bool retreat(){ if(vis[T]) return true; int mi=inf; for(int i=2;i<=tot;++i) if(cap[i] && vis[from[i]] && !vis[to[i]]) mi=min(mi,dis[from[i]]+val[i]-dis[to[i]]); if(mi==inf) return false; for(int i=0;i<=T;++i) if(vis[i]) dis[i]-=mi; return true; } void zkw(){ do { memset(vis,false,sizeof(vis)); agument(S,inf); }while(retreat()); cout<