RE 22pts 有优化dinic 求调
查看原帖
RE 22pts 有优化dinic 求调
465029
Specter_LiZN楼主2025/1/14 21:10

dinic+当前弧优化
只有#1和#2AC,剩下都是RE
用test函数检查过,认为建图没问题
私货注意

#include <bits/stdc++.h>
#define f(i,a,b) for (int i=a;i<=b;++i)
#define buildBoth(x,y,z) build(x,y,z),build(y,x,0)
#define ll long long
#define Reimu cout<<"=Net Graph incident="<<'\n'
const signed N=5e5+5;
const signed M=1e5+5;
const ll Miku=LONG_LONG_MAX;
using namespace std;

struct Edge{
  int nxt,to;
  ll val;
}sav[N];
int head[M],tot=1,n;
int now[M];// 对于节点i的最后一次访问边的编号
int S,T;// 源点,汇点
ll dis[M],ans;
int type,comb;
ll alladd;

void build(int x,int y,ll z){
  tot++;
  sav[tot].nxt=head[x];
  sav[tot].to=y;
  sav[tot].val=z;
  head[x]=tot;
}

bool bfs(){
  f(i,1,n)
    dis[i]=-Miku;
  queue<int> q;
  q.push(S);
  dis[S]=1;
  now[S]=head[S];
  while(!q.empty()){
    int u=q.front();
    q.pop();
    for(int i=head[u];i;i=sav[i].nxt){
      if(sav[i].val==0)
        continue;
      int v=sav[i].to;
      if(dis[v]==-Miku){
        dis[v]=dis[u]+1;
        q.push(v);
        now[v]=head[v];
        if(v==T)
          return 1;
      }
    }
  }
  return 0;
}
ll dfs(int u,ll sum){// sum是整条增广路对最大流的贡献
  if(u==T)
    return sum;
  ll minval=0,res=0;// k是当前最小的剩余容量
  for(int i=now[u];i;i=sav[i].nxt){// 剪枝
    now[u]=i;// 更新当前弧
    if(sav[i].val==0)
      continue;
    int v=sav[i].to;
    if(dis[v]==dis[u]+1){
      minval=dfs(v,min(sum,(ll)sav[i].val));
      if(minval==0)
        dis[v]=-Miku;// 对增广结束的点剪枝
      sav[i].val-=minval;
      sav[i^1].val+=minval;// 反向边
      res+=minval;// 经过该点的所有流量和(流出的总量)
      sum-=minval;// 经过该点的剩余流量
    }
  }
  return res;
}
void test(){
  cout<<n<<'\n';
  // 输出这个图 起点 终点 边权
  f(i,1,n){
    for(int j=head[i];j;j=sav[j].nxt){
      cout<<i<<' '<<sav[j].to<<' '<<sav[j].val<<'\n';
    }
  }
}
signed main(){
  ios::sync_with_stdio(0),cin.tie(0);
  cin>>type;
  S=type+1,T=type+2;
  n=T;
  int tmp;
  f(i,1,type){
    cin>>tmp;
    alladd+=tmp;
    buildBoth(S,i,tmp);
  }
  f(i,1,type){
    cin>>tmp;
    alladd+=tmp;
    buildBoth(i,T,tmp);
  }
  cin>>comb;
  int a,b;
  f(i,1,comb){
    cin>>tmp;
    cin>>a>>b;
    alladd+=a+b;
    n+=2;
    buildBoth(S,n-1,a);
    buildBoth(n,T,b);
    f(j,1,tmp){
      cin>>a;
      buildBoth(n-1,a,Miku);
      buildBoth(a,n,Miku);
    }
  }
  // test();
  while(bfs()){
    ans+=dfs(S,Miku);
  }
  cout<<alladd-ans<<'\n';
  return 0;
  Reimu;
}

2025/1/14 21:10
加载中...