BZOJ 2521: [Shoi2010]最小生成树

这题就是求最少要多少代价可以让一条指定边必为最小生成树上边
每次可以吧某条边权+1 代价为1
可以转化为求去掉权值大于指定边权的边后 最少要多少代价可以使指定边变为割边
即求新图去掉指定边的最小割!!!

每条边的权为V + 1 -line[i].v (要使这条边去掉就是把它升到比指定边权值高)
用最大流水过

发现很久没打网络流了= =、。。
下星期开始怒刷网络流~~~~~~~~~

—————–code——————-

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
#include <ctime>
#include <cstdlib>
#include <sstream>
#include <set>
using namespace std;
typedef long long ll;
const int maxn = 1005;
struct inp
{
  int fr, to, v;
}a[maxn];
struct line
{
  int to, next, v, opt;
}li[100000];
int be[maxn], t, s, n, l, x, m, dinic[maxn], num[maxn];
int sap(int now, int maxf)
{
  if (now == t) return maxf;
  int tot = 0;
  int mi = n;
  for (int i = be[now]; i; i = li[i].next)
  {
    int to = li[i].to;
    if (li[i].v > 0 && dinic[to] + 1 == dinic[now])
    {
      int t = sap(to, min(li[i].v, maxf – tot));
      tot += t;
      li[i].v -= t;
      li[li[i].opt].v += t;
      if (tot == maxf || dinic[s] >= n) return tot;
    }
    if (li[i].v > 0) mi = min(mi, dinic[to]);
  }
  if (!tot)
  {
    if (!–num[dinic[now]])
    {
      dinic[s] = n;
      return 0;
    }
    ++num[dinic[now] = mi + 1];
  }
  return tot;
}
void makeline(int fr, int to, int v, int opt)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].v = v;
  li[l].to = to;
  li[l].opt = opt;
}
int main()
{
  freopen(“input.in”,”r”,stdin);
  freopen(“output.out”,”w”,stdout);
  cin >> n >> m >> x;
  s = 0;
  t = 1000;
  inp va;
  for (int i = 0; i < m; i++)
  {
    scanf(“%d%d%d”, &a[i].fr, &a[i].to, &a[i].v);
    if (i + 1 == x) va = a[i];
  }
  makeline(s, va.fr, 0x7fffffff, l + 2);
  makeline(va.fr, s, 0, l);
  makeline(va.to, t, 0x7fffffff, l + 2);
  makeline(t, va.to, 0, l);
  for (int i = 0; i < m; i++)
    if (a[i].v <= va.v && i + 1 != x)
    {
      makeline(a[i].fr, a[i].to, va.v + 1 – a[i].v, l + 2);
      makeline(a[i].to, a[i].fr, va.v + 1 – a[i].v, l);
    }
  n += 2;
  num[0] = n;
  int ans = 0;
  while (dinic[s] < n) ans += sap(s, 0x7fffffff);
  cout << ans;
  fclose(stdin);fclose(stdout);
}

 

发表评论