提出 #7960310

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
using Int = signed;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;


const int MAX = 5050;
array< pair< int, int >, MAX> v[33];
struct RadixHeap
{
  int size, last;
  array<int, 33> pos;

  RadixHeap() : size(0), last(0) {
    fill(pos.begin(),pos.end(),0);
  }

  bool empty() const { return size == 0; }

  inline int getbit(int a)
  {
    return a ? 32 - __builtin_clz(a) : 0;
  }

  void push(int key, const int &value)
  {
    ++size;
    int bit=getbit(key ^ last);
    v[bit][pos[bit]++]=make_pair(key, value);
  }

  pair< int, int > pop()
  {
    if(pos[0]==0) {
      int idx = 1;
      while(pos[idx]==0) ++idx;
      last = min_element(begin(v[idx]), begin(v[idx])+pos[idx])->first;
      for(auto &p : v[idx]){
        int bit=getbit(p.first ^ last);
        v[bit][pos[bit]++]=p;
      }
      pos[idx]=0;
    }
    --size;
    pos[0]--;
    auto ret = v[0][pos[0]];
    return ret;
  }
};

template<typename TF,typename TC>
struct PrimalDual{
  struct edge{
    int to;
    TF cap;
    TC cost;
    int rev;
    edge(){}
    edge(int to,TF cap,TC cost,int rev):
      to(to),cap(cap),cost(cost),rev(rev){}
  };

  static const TC INF;
  array<vector<edge>, MAX> G;
  array<TC, MAX> h,dist;
  array<int, MAX> prevv,preve;

  void add_edge(int u,int v,TF cap,TC cost){
    G[u].emplace_back(v,cap,cost,G[v].size());
    G[v].emplace_back(u,0,-cost,G[u].size()-1);
  }

  void dijkstra(int s){
    RadixHeap que;
    fill(dist.begin(),dist.end(),INF);

    dist[s]=0;
    que.push(dist[s],s);
    while(!que.empty()){
      auto p=que.pop();
      int v=p.second;
      if(dist[v]<p.first) continue;
      for(int i=0;i<(int)G[v].size();i++){
        edge &e=G[v][i];
        if(e.cap==0) continue;
        if(dist[v]+e.cost+h[v]-h[e.to]<dist[e.to]){
          dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
          prevv[e.to]=v;
          preve[e.to]=i;
          que.push(dist[e.to],e.to);
        }
      }
    }
  }

  TC flow(int s,int t,TF f,int &ok){
    TF flow=0;
    TC res=0;
    fill(h.begin(),h.end(),0);
    while(f>0){
      dijkstra(s);
      if(dist[t]==INF){
        ok=0;
        return res;
      }

      for(int v=0;v<(int)h.size();v++)
        if(dist[v]<INF) h[v]=h[v]+dist[v];

      TF d=f;
      for(int v=t;v!=s;v=prevv[v])
        d=min(d,G[prevv[v]][preve[v]].cap);

      flow+=d;
      f-=d;
      res=res+h[t]*d;
      for(int v=t;v!=s;v=prevv[v]){
        edge &e=G[prevv[v]][preve[v]];
        e.cap-=d;
        G[v][e.rev].cap+=d;
      }
    }
    ok=1;
    return res;
  }
};
template<typename TF, typename TC>
const TC PrimalDual<TF, TC>::INF = numeric_limits<TC>::max()/2;

template<typename TF,typename TC>
struct NegativeEdge{
  PrimalDual<TF, TC> G;
  vector<TF> fs;
  TC sum;
  int S,T;
  NegativeEdge(){}
  NegativeEdge(int n):fs(n+2,0),sum(0),S(n),T(n+1){}

  void use_edge(int u,int v,TF cap,TC cost){
    fs[u]-=cap;
    fs[v]+=cap;
    sum=sum+cost*cap;
  }

  void add_edge(int u,int v,TF cap,TC cost){
    if(cost<TC(0)){
      use_edge(u,v,cap,cost);
      swap(u,v);
      cost=-cost;
    }
    G.add_edge(u,v,cap,cost);
  }

  TC flow(int ts,int tt,TF tf,int &ok){
    fs[ts]+=tf;
    fs[tt]-=tf;

    TF f=0;
    for(int i=0;i<S;i++){
      if(fs[i]>0){
        f+=fs[i];
        G.add_edge(S,i,+fs[i],TC(0));
      }
      if(fs[i]<0){
        G.add_edge(i,T,-fs[i],TC(0));
      }
    }
    return sum+G.flow(S,T,f,ok);
  }
};

//INSERT ABOVE HERE
signed main(){
  int n,m;
  cin>>n>>m;
  NegativeEdge<int, int> G(n+2);

  int cap=n+1;
  for(int i=0;i<m;i++){
    int u,v,l;
    cin>>u>>v>>l;
    u--;v--;
    G.add_edge(v,u,1,l-1);
    if(l==0) cap++;
  }

  for(int i=0;i<n;i++){
    G.add_edge(n,i,cap,+3);
    G.add_edge(i,n,cap,-1);
  }
  int ok=0;
  cout<<-G.flow(n,n,0,ok)<<endl;
  return 0;
}

提出情報

ジャッジ結果