【CF1045A】A Last chance【贪心】【线段树优化建图】【网络流构造方案】_综合

题意：有 $n$ 个武器和 $m$ 个飞船，武器有下面三种

从给定的集合 $S$ 中击破一个。
在给定的区间 $[L,R]$ 中击破一个。
对于给定的 $a,b,c$ ，选择 $0$ 个或 $2$ 个击破。特殊地，每个飞船最多被该操作的 $a,b,c$ 指定一次。

求最多能击破的飞船数量，并输出一种方案。

$n,m\leq 5\times10^3,\sum|S|\leq10^5$

网络流大杂烩

操作 $3$ 似乎是个经典的不可做问题。但注意到指定的三个飞船不会重复，且只有 $3$ 能选 $2$ 个，可以贪心地把所有 $3$ 都覆盖（也可以通过后面的建图理解为什么贪心是正确的）

$1、3$ 操作直接建， $2$ 操作建个线段树优化建图

具体而言，先整一棵线段树，树上的父结点向儿子连容量为 INF 的边，叶子结点表示飞船，向 $T$ 连容量为 $1$ 。另开 $n$ 个点，表示武器， $1$ 操作流 $1$ 的流量直接连， $2$ 操作拆成 $\log$ 个区间连， $3$ 操作流 $2$ 的流量先记下来最后连上去，这样 $3$ 操作会最先增广，然后后面无论怎么增广流量都是 $2$ (这也是为什么贪心是对的)

方案可以从 $T$ 往回dfs，走有流的边。因为已经有流了，所以往这条边走一定有合法方案，走到武器点的时候立刻返回，并顺便退掉 $1$ 的流量。

~~谁能告诉我怎么算数组大小啊~~

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <queue>
#define MAXN 1000005
#define MAXM 10000005
using namespace std;
const int INF=0x7fffffff;
struct edge{int u,v,c;}e[MAXN];
int head[MAXN],cur[MAXN],nxt[MAXM],cnt=1;
void insert(int u,int v,int c)
{e[++cnt]=(edge){u,v,c};nxt[cnt]=head[u];head[u]=cnt;
}
void addnode(int u,int v,int c){insert(u,v,c),insert(v,u,0);}
int dis[MAXN],S,T;
bool bfs()
{queue<int> q;q.push(S);memset(dis,-1,(T+5)*sizeof(int));dis[S]=0;while (!q.empty()){int u=q.front();q.pop();for (int i=head[u];i;i=nxt[i])if (e[i].c&&dis[e[i].v]==-1){dis[e[i].v]=dis[u]+1;q.push(e[i].v);if (e[i].v==T) return true;}}return false;
}
int dfs(int u,int f)
{if (u==T||!f) return f;int used=0;for (int &i=cur[u];i;i=nxt[i])if (e[i].c&&dis[e[i].v]==dis[u]+1){int w=dfs(e[i].v,min(f,e[i].c));if (!w) continue;used+=w,f-=w;e[i].c-=w,e[i^1].c+=w;if (!f) break;}if (!used) dis[u]=-1;return used;
}
inline int dinic()
{int mflow=0;while (bfs()) memcpy(cur,head,(T+5)*sizeof(int)),mflow+=dfs(S,INF);return mflow;
}
int pos[MAXN],sop[MAXN],mx;
#define lc p<<1
#define rc p<<1|1
void build(int p,int l,int r)
{mx=max(mx,p);if (l==r) return (void)(pos[l]=p,sop[p]=l);int mid=(l+r)>>1;build(lc,l,mid);build(rc,mid+1,r);addnode(p,lc,INF),addnode(p,rc,INF);
}
void query(int p,int l,int r,int ql,int qr,int u)
{if (ql<=l&&r<=qr) return (void)addnode(u,p,1);if (qr<l||r<ql) return;int mid=(l+r)>>1;query(lc,l,mid,ql,qr,u),query(rc,mid+1,r,ql,qr,u);
}
int x[MAXN],a[MAXN],b[MAXN],c[MAXN],tot,n,m;
int ans[MAXN];
int find(int u,int f)
{if (mx+1<=u&&u<=mx+n) return u;for (int i=head[u];i;i=nxt[i])if (e[i].c&&e[i].v!=f){--e[i].c;++e[i^1].c;return find(e[i].v,u);}return 0;
}
int main()
{scanf("%d%d",&n,&m);build(1,1,m);S=mx+n+1,T=S+1;for (int i=1;i<=n;i++){int type;scanf("%d",&type);if (type==0){addnode(S,mx+i,1);int k;scanf("%d",&k);while (k--){int x;scanf("%d",&x);addnode(mx+i,pos[x],1);}}if (type==1){addnode(S,mx+i,1);int l,r;scanf("%d%d",&l,&r);query(1,1,m,l,r,mx+i);}if (type==2){++tot;x[tot]=i;scanf("%d%d%d",&a[tot],&b[tot],&c[tot]);}}for (int i=1;i<=tot;i++){addnode(S,mx+x[i],2);addnode(mx+x[i],pos[a[i]],1);addnode(mx+x[i],pos[b[i]],1);addnode(mx+x[i],pos[c[i]],1);}for (int i=1;i<=m;i++) addnode(pos[i],T,1);printf("%d\n",dinic());for (int i=head[T];i;i=nxt[i])if (e[i].c){int t=find(e[i].v,T);if (t) printf("%d %d\n",t-mx,sop[e[i].v]);}return 0;
}