WA两个点,求助
查看原帖
WA两个点,求助
288716
lzqy_楼主2020/7/22 11:21
#include <bits/stdc++.h>
using namespace std;
vector<int>v[5001];//记录边
vector<int>w[5001];//记录流量
vector<int>ww[5001];//记录边权
int a[5001][5001];//记录反边的序号
int MAX=INT_MAX>>1;
int n,m,S,T;
int d[5001];//SPFA
bool K[5001];
int ans;
inline int read()                        //以字符串形式读入数字可提速
{
  int x=0;
  char c=getchar();
  for(; c<'0'  || c>'9';  c=getchar());
  for(; c<='9' && c>='0'; c=getchar())
    x=(x<<3)+(x<<1)+c-'0';               //位运算优化即x*8+x*2=x*10
  return x;
}
int min(int a,int b)
{
  if(a>b)
    return b;
  return a;
}
int max(int a,int b)
{
  if(a<b)
    return b;
  return a;
}
bool spfa()
{
  bool kk[5001];
  queue<int>q;
  q.push(S),kk[S]=1;
  for(int i=1; i<=n; i++)
    d[i]=MAX;
  d[S]=0;
  while(!q.empty())
  {
    int t=q.front();
    q.pop(),kk[t]=0;
    for(int i=0; i<v[t].size(); i++)
    {
      if(d[v[t][i]]>d[t]+ww[t][i] && w[t][i])
      {
        d[v[t][i]]=d[t]+ww[t][i];
        if(kk[v[t][i]]==0)
          q.push(v[t][i]),kk[v[t][i]]=1;
      }
    }
  }
  if(d[T]==MAX)
    return 0;
  return 1;
}
int dfs(int dian,int liu)
{
  if(dian==T)
    return liu;
  int SUM=liu;
  K[dian]=1;
  for(int i=0; i<v[dian].size(); i++)
  {
    if(w[dian][i]&&d[v[dian][i]]==d[dian]+ww[dian][i]&&K[v[dian][i]]==0)
    {
      int d=dfs(v[dian][i],min(SUM,w[dian][i]));
      w[dian][i]-=d,w[v[dian][i]][a[dian][v[dian][i]]]+=d;
      SUM-=d;
      ans+=d*ww[dian][i];
      if(SUM==0)
        break;
    }
  }
  K[dian]=0;
  return liu-SUM;
}
int dinic()
{
  int ANS=0;
  while(spfa())
  {
    for(int i=1; i<=n; i++)K[i]=0;
    ANS+=dfs(S,INT_MAX);
  }

  return ANS;
}
int main()
{
  n=read(),m=read(),S=read(),T=read();
  int x,y,z,Z;
  while(m--)
  {
    x=read(),y=read(),z=read(),Z=read();
    v[x].push_back(y),v[y].push_back(x);
    w[x].push_back(z),w[y].push_back(0);
    ww[x].push_back(Z),ww[y].push_back(-Z);
    a[x][y]=v[y].size()-1,a[y][x]=v[x].size()-1;
  }
  int dddd=dinic();
  cout<<dddd<<" "<<ans;
  return 0;
}

调得【数据删除】了,求大佬帮忙qwq

2020/7/22 11:21
加载中...