hdu-携程复赛-最短路径的代价-抠图+最小割

被数据范围坑死了。。。

说好的m<=10000,改成了m<=11000....

把所有最短路涉及到的边抠出来。

然后建图，边的权值为边的c。

然后对图求一个最小割。

最小割割掉的所有的边即为要选调的边。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
      
        using namespace std; #define INF 99999999 const int maxn =1110; const int maxm =25000; const int oo = 1<<29; struct Arclist { int cnt, head[maxn], dis[maxn]; int cur[maxn], pre[maxn], gap[maxn], aug[maxn]; struct node { int u, v, w, next; } edge[maxm]; void init(int n) { cnt = 0; std::fill_n(head, n+1, -1); } void add(int u, int v, int w) { edge[cnt].u = u; edge[cnt].v = v; edge[cnt].w = w; edge[cnt].next = head[u]; head[u] = cnt++; edge[cnt].u = v; edge[cnt].v = u; edge[cnt].w = 0; edge[cnt].next = head[v]; head[v] = cnt++; } int sap(int s, int e, int n) { int max_flow = 0, u = s; int mindis; for(int i = 0; i <= n; i++) { cur[i] = head[i]; dis[i] = 0; gap[i] = 0; } aug[s] = oo; pre[s] = -1; gap[0] = n; while(dis[s]
       
        0 && dis[u]==dis[v]+1) { flag = true; pre[v] = u; cur[u] = id; aug[v] = std::min(aug[u], edge[id].w); u = v; break; } } if(flag==false) { if(--gap[dis[u]]==0) break; mindis = n; cur[u] = head[u]; for(int id = head[u]; id != -1; id = edge[id].next) { int v = edge[id].v; if(edge[id].w>0 && dis[v]
        
         dis[i]) { minn=dis[i]; x=i; } } if(minn==INF)break; vis[x]=1; for(i=gs.head[x];i!=-1;i=gs.edge[i].next) { int v=gs.edge[i].v; int w=gs.edge[i].w; if(vis[v])continue; if(dis[v]>dis[x]+w)dis[v]=dis[x]+w; } } //for(i=1;i<=n;i++)cout<
         
          que; while(!que.empty())que.pop(); que.push(ed); memset(vis,0,sizeof(vis)); vis[ed]=1; while(!que.empty()) { int x=que.front(); que.pop(); if(x==st)continue; for(i=gs.head[x];i!=-1;i=gs.edge[i].next) { int u=gs.edge[i].v; int w=gs.edge[i].w; int c=gs.edge[i].c; if(dis[u]+w==dis[x]) { // cout<