题解 P1640 【[SCOI2010]连续攻击游戏】

· · 题解

这道题从网络流的角度来想，是很神奇的。

它告诉我们一个技巧：玄学复杂度分析（按特定顺序退流/增广）

首先建立模型。

满足连续攻击条件不太好搞，我们转化成判定性问题。

即“能否连续攻击limit次”

(1)每个物品只能使用一次

(2)攻击->价值(流)

那么可以这样建图：

分为两层,一层是每个物品,第二层是按属性值排序的每次攻击。

(1)从S向代表每个物品的点连一条边，容量为1(每个物品只能使用一次);

(2)从每个物品向（属性1）（属性2）两个第二层的点连边。

(3)每个第二层的点向T连边，容量为1(每种属性只攻击一次)

这样子，我们成功的使用一个O(\text{网络流}*log(10000))的算法解决了本题。

无疑是会TLE的。

我们知道在跑网络流的时候，增广的路径是玄学。

根据人类智慧，S的出边多，T的出边少，从S开始找可能会慢。

那我们把整个图反向，这样最大流不变。

我们从原来的T开始增广的话，根据人类智慧，增广顺序是可以随意指定的，这样并不会被卡。

于是可以按照增广属性1，属性2，属性3……的顺序。

然后，我们发现，这就相当于我们从小到大枚举答案，然后利用上一次的残量网络来增广（具体见代码）。

我们知道，要么增广出1，要么无法增广，不会出现拆前面的流的情况。

这样子，复杂度就从O(\text{网络流}*log(10000))变为了O(\text{网络流})!

玄学

顺便说一句，我使用vector建边MLE，然后使用了一个比较神奇的建边方法。

还有，我懒得写dinic，于是乎写了FF最大流（FF过百万吼！）。

// luogu-judger-enable-o2
#include<cstdio>
#include<vector>
#define Maxn 1010000
using namespace std;
int n,m,sink,em,ans;
struct Line
{int g,l,b;}
l[Maxn*6];
int s[Maxn+100];
int cnt,e[Maxn+100];
int dfs(int num,int val)
{
  if (num==sink)return val;
  e[num]=cnt;
  int flow,v;
  for (int i=s[num-1];i<s[num];i++)
   if (l[i].l&&e[v=l[i].g]!=cnt){
    flow=dfs(v,min(val,l[i].l));
    if (flow){
      l[i].l-=flow;
      l[l[i].b].l+=flow;
      return flow;
    }
  }return 0;
}
void addLine(int f,int t,int c)
{
  l[s[f]].b=s[t];
  l[s[t]].b=s[f];
  l[s[f]].g=t;
  l[s[f]].l=c;
  l[s[t]].g=f;
  l[s[t]].l=0;
  s[t]++;s[f]++;
}
struct Data
{int a,b;}
a[1000500];
int main()
{
  scanf("%d",&n);
  sink=n+10010+1;
  //点1~n是物品，点n+1~n+10000是属性值
  //sink是汇，没有源
  for (int i=1;i<=n;i++){
    scanf("%d%d",&a[i].a,&a[i].b);
    s[sink]++;s[i]=3;
    s[n+a[i].a]++;
    s[n+a[i].b]++;
  }for (int i=2;i<=sink;i++)s[i]+=s[i-1];
  for (int i=sink;i>=0;i--)s[i+1]=s[i];
  for (int i=1;i<=n;i++)addLine(i,sink,1);
  for (int i=1;i<=n;i++){
    addLine(n+a[i].a,i,1);
    addLine(n+a[i].b,i,1);
  }cnt=1;
  for (int i=1;i<=10010;i++,cnt=i)
   if (!dfs(n+i,1))
    {printf("%d",i-1);break;}
  return 0;
}

突然想到，FF跑二分图匹配不就是匈牙利吗？