图片说明

  • 题意：
  • 给出一个无向连通图，每条边的权值都是1，可存在重边，a在1节点，b在n节点。
  • 问你最少花费多少代价能将1到n的路径最远，如果不存在路径，输出0就行
  • 题解：
  • 先求出最短路，然后保留所有满足 dey dex = ew 的边，对于新的图求 1 到 n 的最小
  • 割即为答案，最小割模板第一次用。
  • 代码：
    #include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e16;
const int maxx = 1e4+5;
const int inf_int = 1e9+5;
struct node{
  ll d;
  int x;
  bool operator<(const node &b)const
  {
      return d>b.d;
  }
};
int n,m,xx[maxx],yy[maxx],cc[maxx];
vector< pair<int,int> > GG[maxx];
priority_queue<node> q;
bool vis[maxx];
ll dis[maxx],dis2[maxx];
void dijk(int s,ll *d)
{
  int u,v,w,len;
  node tmp;
  memset(vis,0,sizeof(vis));
  for(int i=1;i<=n;i++)
      d[i] = inf;
  d[s] = 0;
  q.push((node){0,s});
  while(!q.empty())
  {
      tmp = q.top();
      q.pop();
      u = tmp.x;
      if(vis[u])
          continue;
      vis[u] = true;
      len = GG[u].size();
      for(int i=0;i<len;i++)
      {
          v=GG[u][i].first;
          w=GG[u][i].second;
          if(d[v] > d[u]+w)
          {
              d[v]=d[u]+w;
              q.push((node){d[v],v});
          }
      }
  }
  return ;
}
//最大流和最小割模板
struct edge{
  int to,cap,rev;
};
vector<edge> G[maxx];
int leval[maxx];
int iter[maxx];
void add(int from,int to,int cap)
{
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
  return ;
}
void bfs(int s)
{
  memset(leval,-1,sizeof(leval));
  queue<int> que;
  leval[s] = 0;
  que.push(s);
  while(!que.empty())
  {
      int v = que.front();
      que.pop();
      for(int i=0;i<G[v].size();i++)
      {
          edge &e=G[v][i];
          if(e.cap>0&&leval[e.to]<0)
          {
              leval[e.to]=leval[v]+1;
              que.push(e.to);
          }
      }
  }
  return ;
}
int dfs(int v,int t,int f)
{
  if(v==t)
      return f;
  for(int &i=iter[v];i<G[v].size();i++)
  {
      edge &e = G[v][i];
      if(e.cap>0&&leval[v]<leval[e.to])
      {
          int d=dfs(e.to,t,min(f,e.cap));
          if(d>0)
          {
              e.cap -=d;
              G[e.to][e.rev].cap+=d;
              return d;
          }
      }
  }
  return 0;
}
int Dinic(int s,int t)
{
  int flow=0;
  while(1)
  {
      bfs(s);
      if(leval[t]<0)
          return flow;
      memset(iter,0,sizeof(iter));
      int f;
      while((f=dfs(s,t,inf_int))>0)
          flow+=f;
  }
}
int main()
{
  int t;
  cin>>t;
  while(t--)
  {
      cin>>n>>m;
      for(int i=1;i<=m;i++)
      {
          scanf("%d%d%d",&xx[i],&yy[i],&cc[i]);
          GG[xx[i]].push_back( pair<int,int>(yy[i],cc[i]) );
      }
      dijk(1,dis);
      for(int i=1;i<=n;i++)
          GG[i].clear();
      for(int i=1;i<=m;i++)
          GG[yy[i]].push_back( pair<int,int>(xx[i],cc[i]) );
      dijk(n,dis2);
      for(int i=1;i<=m;i++)
      {
          if(dis[xx[i]] + cc[i] + dis2[yy[i]] == dis[n])
              add(xx[i],yy[i],cc[i]);
      }//构建一个新的图
      cout<<Dinic(1,n)<<endl;
      for(int i=1;i<=n;i++)
      {
          GG[i].clear();
          G[i].clear();
      }
  }
  return 0;
}