题意很难读。比赛时读了半个小时，赛后又读了一个小时，还是有些模棱两可。最后又问了问，大概知道是什么意思了。
就是给定一些航班，每个航班双向连接一对城市。要求从西安出发，必须先到达上海然后到达青岛，然后从青岛回到上海浦东机场的最小费用
其中，每个机场有登机区和降落区，每个机场的登机区和降落区都只能经过一次。上海有浦东机场和虹桥机场两个，两个机场间可以不坐飞机并且不消耗费用
对于点容量限制，可以通过拆点来限制点容量，这是基本操作
对于路径限制，可以通过源点汇点的设定来做到。若最大流为满则存在路径
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+8;
const int INF=0x7f7f7f7f;
struct fuck{
int u,v,cap,w,next;
}edge[maxn<<4];
int head[maxn<<1];
int tol;
void init()
{
tol=0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int cap)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol].cap=cap;
edge[tol].w=w;
edge[tol].next=head[u];
head[u]=tol++;
edge[tol].u=v;
edge[tol].v=u;
edge[tol].w=-w;
edge[tol].cap=0;
edge[tol].next=head[v];
head[v]=tol++;
}
map<string,int> mp;
int idx;
int getid(char s[])
{
if(mp.count(s)!=0)
return mp[s];
mp[s]=idx;addedge(idx*2-1,idx*2,0,1);idx++;
return idx-1;
}
int dis[maxn<<1],pre[maxn<<1];
bool vis[maxn<<1];
bool spfa(int sour,int sink)
{
queue<int> q;
q.push(sour);
memset(dis,INF,sizeof(dis));
memset(vis,false,sizeof(vis));
dis[sour]=0;vis[sour]=true;pre[sour]=-1;
int i,u,v;
while(!q.empty())
{
u=q.front();q.pop();
vis[u]=false;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(edge[i].cap>0&&edge[i].w+dis[u]<dis[v])
{
dis[v]=dis[u]+edge[i].w;
pre[v]=i;
if(!vis[v])
vis[v]=true,q.push(v);
}
}
}
if(dis[sink]>=INF) return false;
return true;
}
void Minicost(int sour,int sink)
{
int co,fl;
co=fl=0;
while(spfa(sour,sink))
{
int mi=INF;
for(int i=pre[sink];i!=-1;i=pre[edge[i^1].v]){
if(mi>edge[i].cap)
mi=edge[i].cap;
}
for(int i=pre[sink];i!=-1;i=pre[edge[i^1].v]){
edge[i].cap-=mi;
edge[i^1].cap+=mi;
}
fl+=mi;
co+=dis[sink]*mi;
}
if(fl==3)
printf("%d
",co);
else
printf("-1
");
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int m;
scanf("%d",&m);
init();idx=1;
mp.clear();
mp["Xian"]=idx;addedge(idx*2-1,idx*2,0,1);idx++;
mp["Qingdao"]=idx;addedge(idx*2-1,idx*2,0,2);idx++;
mp["Hongqiao"]=idx;addedge(idx*2-1,idx*2,0,2);idx++;
mp["Pudong"]=idx;addedge(idx*2-1,idx*2,0,1);idx++;
while(m--)
{
char s[12],c[12];
int w;
scanf("%s%s%d",s,c,&w);
int u=getid(s);
int v=getid(c);
addedge(u*2,v*2-1,w,INF);
addedge(v*2,u*2-1,w,INF);
}
int sour=0,sink=idx*2-1;
addedge(sour,3*2-1,0,2);
addedge(sour,4*2-1,0,1);
addedge(1*2,sink,0,1);
addedge(2*2,sink,0,2);
Minicost(sour,sink);
}
return 0;
}