类似于一种可撤销的贪心，不难想到这是费用流的模型。
考虑到我们实际会用到的边比实际的边少很多，我们可以动态建边，以减少空间的使用，即当流过了一条边之后再建立第二次流过需要的边（如果有第二次的话）。
然后建立超级源点和超级汇点，跑个费用流就可以了..
1 #include <iostream>神奇的代码
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #define M 4000105
6 #define N 1005
7 using namespace std;
8 bool visit[N];
9 int head[N],pre[N],num,n,m,k,s,dis[N],team[M*2],l,r,ans;
10 struct data{
11 int next,to,flow,power,st,a,c,er;
12 }line[M];
13 void add(int u,int v,int x,int y,int z,int w){
14 num++;
15 line[num].st=u;
16 line[num].to=v;
17 line[num].next=head[u];
18 line[num].flow=w;
19 line[num].power=x+y;
20 line[num].a=x;
21 line[num].c=z;
22 line[num].er=num+1;
23 head[u]=num;
24 num++;
25 line[num].st=v;
26 line[num].to=u;
27 line[num].next=head[v];
28 line[num].flow=0;
29 line[num].power=-x-y;
30 line[num].a=x;
31 line[num].c=z;
32 line[num].er=num-1;
33 head[v]=num;
34 }
35 void SPFA(){
36 int u=0;
37 l=0,r=1;
38 team[1]=0;
39 visit[0]=true;
40 dis[0]=0;
41 while (l<r){
42 u=team[++l];
43 for (int v=0,i=head[u];i;i=line[i].next){
44 v=line[i].to;
45 if ((dis[v]>dis[u]+line[i].power)&&(line[i].flow)){
46 dis[v]=dis[u]+line[i].power;
47 pre[v]=i;
48 if (visit[v]==false){
49 team[++r]=v;
50 visit[v]=true;
51 }
52 }
53 visit[u]=false;
54 }
55 }
56 if (pre[n+1]==-1) ans=-1;
57 }
58 void solve(){
59 ans+=dis[n+1];
60 int i=pre[line[pre[n+1]].st];
61 do{
62 line[i].flow--;
63 line[line[i].er].flow++;
64 line[i].c--;
65 if (line[i].c>0)
66 add(line[i].st,line[i].to,line[i].a,line[i].power,line[i].c,1);
67 line[i].c=0;
68 line[line[i].er].c=0;
69 i=pre[line[i].st];
70 }while (line[i].to!=1);
71 }
72 int main(){
73 freopen("game.in","r",stdin);
74 freopen("game.out","w",stdout);
75 scanf("%d%d%d%d",&n,&m,&k,&s);
76 num=0;
77 add(0,1,0,0,99999999,99999999);
78 for (int u,i=1;i<=s;++i){
79 scanf("%d",&u);
80 add(u,n+1,0,0,99999999,99999999);
81 }
82 for (int i=1,u,v,x,y,z;i<=m;i++){
83 scanf("%d%d%d%d%d",&u,&v,&x,&y,&z);
84 add(u,v,x,y,z,1);
85 }
86 ans=0;
87 while (k--){
88 for (int i=0;i<=n+1;++i)
89 dis[i]=99999999,visit[i]=false;
90 pre[n+1]=-1;
91 SPFA();
92 if (ans==-1) break;
93 solve();
94 }
95 printf("%d\n",ans);
96 return 0;
97 }
改了一个晚上终于发现原来一条边流完后建立另一条边时原来边的C值（可流过次数）要清零QAQ）
当时考试的时候看出来是网络流不想写随便写了个SPFA水了水...