題意：
給你一個(gè)圖 讓你求經(jīng)過(guò)所有點(diǎn)的一條最短路徑 終點(diǎn)無(wú)所謂
做法：
有人竟然費(fèi)用流屎過(guò)。。
我的做法是上下界費(fèi)用流
A->A' 下界是1 然后就建圖了
1 #include <cstdio>
2 #include <cstring>
3 #define min(a,b) ((a)<(b)?(a):(b))
4 #define n 2047
5 #define e 300005
6 int vtx[e],w[e],f[e],ne[e],tot=1;
7 int L[n],q[n+1],pre[n],d[n],N,M,hidden,S,T,SuperS,SuperT,Cost;
8 bool vis[n];
9 inline void Ins(int u,int v,int fl,int cost)
10 {
11 vtx[++tot]=v;f[tot]=fl;w[tot]=cost;ne[tot]=L[u];L[u]=tot;
12 vtx[++tot]=u;f[tot]=0;w[tot]=-cost;ne[tot]=L[v];L[v]=tot;
13 }
14 inline bool spfa()
15 {
16 memset(vis,0,sizeof(vis));
17 memset(d,63,sizeof(d));
18 d[q[1]=SuperS]=0,vis[SuperS]=1;
19 for (int h=0,t=1,u;h!=t;vis[u]=0)
20 {
21 u=q[h=(h+1)&n];
22 for (int p=L[u],v=vtx[p];p;v=vtx[p=ne[p]])
23 if (f[p]&&d[u]+w[p]<d[v])
24 {
25 d[v]=d[u]+w[p],pre[v]=p;
26 if (!vis[v]) vis[q[t=(t+1)&n]=v]=1;
27 }
28 }
29 return d[SuperT]<1<<29;
30 }
31 inline void push()
32 {
33 int fl=1<<30;
34 for (int i=SuperT;i!=SuperS;i=vtx[pre[i]^1])
35 fl=min(fl,f[pre[i]]);
36 Cost+=d[SuperT]*fl;
37 for (int i=SuperT;i!=SuperS;i=vtx[pre[i]^1])
38 f[pre[i]]-=fl,f[pre[i]^1]+=fl;
39 }
40 int main()
41 {
42 int u,v,w;
43 freopen("starrace.in","r",stdin);
44 freopen("starrace.out","w",stdout);
45 scanf("%d%d",&N,&M);
46 hidden=2*N+1;
47 S=hidden+1,T=S+1,SuperS=T+1,SuperT=SuperS+1;
48 Ins(S,hidden,1,0);
49 for (int i=1;i<=N;++i)
50 {
51 scanf("%d",&w);
52 Ins(hidden,i,1,w);
53 Ins(i+N,hidden,1,0);
54 Ins(i+N,T,1,0);
55 Ins(SuperS,i+N,1,0);
56 Ins(i,SuperT,1,0);
57 }
58 Ins(T,S,1<<30,0);
59 for (int i=1;i<=M;++i)
60 {
61 scanf("%d%d%d",&u,&v,&w);
62 if (u>v) {int t=u;u=v;v=t;}
63 Ins(u+N,v,1,w);
64 }
65 for (;spfa();push());
66 printf("%d\n",Cost);
67 return 0;
68 }
69