题意：
思路：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 typedef long long ll; 6 using namespace std; 7 #define N 310000 8 #define oo 1000000000 9 10 bool inq[N]; 11 ll s[N]; 12 int f[300][300],head[N],vet[N],len1[N],len2[N],nxt[N],dis[N],q[N],a[N], 13 pre[N][3],fan[N],n,tot,cnt,source,src,num; 14 15 void add(int a,int b,int c,int d) 16 { 17 nxt[++tot]=head[a]; 18 vet[tot]=b; 19 len1[tot]=c; 20 len2[tot]=d; 21 head[a]=tot; 22 23 nxt[++tot]=head[b]; 24 vet[tot]=a; 25 len1[tot]=0; 26 len2[tot]=-d; 27 head[b]=tot; 28 } 29 30 bool spfa() 31 { 32 for(int i=1;i<=cnt;i++) 33 { 34 dis[i]=oo; 35 inq[i]=false; 36 } 37 int t=0; int w=1; 38 q[1]=source; dis[source]=0; inq[source]=true; 39 while(t<w) 40 { 41 t++; int u=q[t%(cnt+5)]; inq[u]=false; 42 int e=head[u]; 43 while(e) 44 { 45 int v=vet[e]; 46 if(len1[e]&&dis[u]+len2[e]<dis[v]) 47 { 48 dis[v]=dis[u]+len2[e]; 49 pre[v][1]=u; 50 pre[v][2]=e; 51 if(!inq[v]) 52 { 53 w++; q[w%(cnt+5)]=v; inq[v]=true; 54 } 55 } 56 e=nxt[e]; 57 } 58 } 59 60 if(dis[src]==oo) return false; 61 a[++num]=dis[src]; 62 return true; 63 } 64 65 void mcf() 66 { 67 int k=src; 68 int t=oo; 69 while(k!=source) 70 { 71 int e=pre[k][2]; 72 t=min(t,len1[e]); 73 k=pre[k][1]; 74 } 75 k=src; 76 while(k!=source) 77 { 78 int e=pre[k][2]; 79 len1[e]-=t; 80 len1[fan[e]]+=t; 81 k=pre[k][1]; 82 } 83 84 } 85 86 int main() 87 { 88 //freopen("parade.in","r",stdin); 89 //freopen("parade.out","w",stdout); 90 for(int i=1;i<=N;i++) 91 if(i&1) fan[i]=i+1; 92 else fan[i]=i-1; 93 int m,Q; 94 scanf("%d%d%d",&n,&m,&Q); 95 for(int i=1;i<=n;i++) 96 for(int j=1;j<=n;j++) f[i][j]=oo; 97 for(int i=1;i<=n;i++) f[i][i]=0; 98 source=n+n+1; src=source+1; cnt=src; 99 memset(head,0,sizeof(head)); 100 tot=0; 101 for(int i=1;i<=n;i++) 102 { 103 add(source,i,1,0); 104 add(i+n,src,1,0); 105 } 106 for(int i=1;i<=m;i++) 107 { 108 int x,y,z; 109 scanf("%d%d%d",&x,&y,&z); 110 f[x][y]=min(f[x][y],z); 111 } 112 for(int i=1;i<=n;i++) 113 for(int j=1;j<=n;j++) 114 for(int k=1;k<=n;k++) f[j][k]=min(f[j][k],f[j][i]+f[i][k]); 115 116 for(int i=1;i<=n;i++) 117 for(int j=1;j<=n;j++) 118 if(i!=j&&f[i][j]<=10000) add(i,j+n,1,f[i][j]); 119 num=0; 120 while(spfa()) mcf(); 121 s[0]=0; 122 num=min(num,n); 123 for(int i=1;i<=num;i++) 124 { 125 //printf("%d ",a[i]); 126 s[i]=s[i-1]+a[i]; 127 } 128 printf(" "); 129 for(int i=1;i<=Q;i++) 130 { 131 ll x; 132 scanf("%lld",&x); 133 int l=0; 134 int r=num; 135 int last=0; 136 while(l<=r) 137 { 138 int mid=(l+r)>>1; 139 if(a[mid]<x){last=mid; l=mid+1;} 140 else r=mid-1; 141 } 142 ll ans=x*(n-last)+s[last]; 143 printf("%lld ",ans); 144 } 145 return 0; 146 } 147 148 149 150