首页 > 代码库 > 数据结构板子
数据结构板子
目录
树状数组... 1
线段树... 3
树链剖分... 5
主席树... 11
字典树Trie树... 12
加权并查集... 15
二分图... 18
树状数组
(pos^(pos-1))&pos==pos&(-pos)两种写法都行
单点添加，区间查询
#include<cstdio>
#include<iostream>
#define M 500010
using namespace std;
int a[M],tarr[M],n,m;
int Qry_tarr(int pos)
{
int sum=0;
while(pos)
{
sum+=tarr[pos];
pos-=(pos^(pos-1))&pos;
}
return sum;
}
void Add_tarr(int pos,int delta)
{
while(pos<=n)
{
tarr[pos]+=delta;
pos+=(pos^(pos-1))&pos;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
Add_tarr(i,a[i]);
int flag,x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&flag,&x,&y);
if(flag==1)Add_tarr(x,y);
else printf("%d\n",Qry_tarr(y)-Qry_tarr(x-1));
}
return 0;
}
区间修改，单点查询（差分）
#include<iostream>//区间修改，单点查询
using namespace std;
#define M 500010
int tr[M],b[M],n;
int search(int pos)
{
int sum=0;
while(pos)
{
sum+=tr[pos];
pos-=(pos^(pos-1))&pos;
}
return sum;
}
void add(int pos,int v)
{
while(pos<=n)
{
tr[pos]+=v;
pos+=(pos^(pos-1))&pos;
}
}
int main()
{
cin>>n;
int a=0,c=0;
for(int i=1;i<=n;i++)
{
cin>>a;
b[i]=a-c;
c=a;
}
for(int i=1;i<=n;i++)
add(i,b[i]);
cin>>a;
cout<<search(a);
}
线段树
线段树5种基本操作代码：
#include<cstdio>
using namespace std;
int n,p,a,b,m,x,y,ans;
struct node
{
int l,r,w,f;
}tree[400001];
inline void build(int k,int ll,int rr)//建树
{
tree[k].l=ll,tree[k].r=rr;
if(tree[k].l==tree[k].r)
{
scanf("%d",&tree[k].w);
return;
}
int m=(ll+rr)/2;
build(k*2,ll,m);
build(k*2+1,m+1,rr);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void down(int k)//标记下传
{
tree[k*2].f+=tree[k].f;
tree[k*2+1].f+=tree[k].f;
tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
tree[k].f=0;
}
inline void ask_point(int k)//单点查询
{
if(tree[k].l==tree[k].r)
{
ans=tree[k].w;
return ;
}
if(tree[k].f) down(k);
int m=(tree[k].l+tree[k].r)/2;
if(x<=m) ask_point(k*2);
else ask_point(k*2+1);
}
inline void change_point(int k)//单点修改
{
if(tree[k].l==tree[k].r)
{
tree[k].w+=y;
return;
}
if(tree[k].f) down(k);
int m=(tree[k].l+tree[k].r)/2;
if(x<=m) change_point(k*2);
else change_point(k*2+1);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void ask_interval(int k)//区间查询
{
if(tree[k].l>=a&&tree[k].r<=b)
{
ans+=tree[k].w;
return;
}
if(tree[k].f) down(k);
int m=(tree[k].l+tree[k].r)/2;
if(a<=m) ask_interval(k*2);
if(b>m) ask_interval(k*2+1);
}
inline void change_interval(int k)//区间修改
{
if(tree[k].l>=a&&tree[k].r<=b)
{
tree[k].w+=(tree[k].r-tree[k].l+1)*y;
tree[k].f+=y;
return;
}
if(tree[k].f) down(k);
int m=(tree[k].l+tree[k].r)/2;
if(a<=m) change_interval(k*2);
if(b>m) change_interval(k*2+1);
tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
int main()
{
scanf("%d",&n);//n个节点
build(1,1,n);//建树
scanf("%d",&m);//m种操作
for(int i=1;i<=m;i++)
{
scanf("%d",&p);
ans=0;
if(p==1)
{
scanf("%d",&x);
ask_point(x);//单点查询,输出第x个数
printf("%d",ans);
}
else if(p==2)
{
scanf("%d%d",&x,&y);
change_point(1);//单点修改
}
else if(p==3)
{
scanf("%d%d",&a,&b);//区间查询
ask_interval(1);
printf("%d\n",ans);
}
else
{
scanf("%d%d%d",&a,&b,&y);//区间修改
change_interval(1);
}
}
}
树链剖分
【题目描述】
给你由N个结点组成的树。树的节点被编号为1到N，边被编号为1到N-1。每一条边有一个权值。然后你要在树上执行一系列指令。指令可以是如下三种之一：
CHANGE i v：将第i条边的权值改成v。
NEGATE a b：将点a到点b路径上所有边的权值变成其相反数。
QUERY a b：找出点a到点b路径上各边的最大权值。
【输入格式】
输入文件的第一行有一个整数N（N<=10000）。
接下来N-1行每行有三个整数a,b,c，代表点a和点b之间有一条权值为c的边。这些边按照其编号从小到大给出。
接下来是若干条指令（不超过10^5条），都按照上面所说的格式。
输入文件的最后一行是"DONE".
【输出格式】
对每个“QUERY”指令，输出一行，即路径上各边的最大权值。
【样例输入】
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
【样例输出】
1
3
【来源】
POJ 3237 Tree
难点在于取相反数操作
记录下最大值和最小值，有取相反数操作时，就把两个值变成相反数，再交换两数的值就ok，然后给这个区间打上标记（线段树的lazy标记），以后访问或更改值时记得下传标记就好。
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100010;
struct Edge{
int to,next;
}edge[MAXN*2];
int head[MAXN],tot;
int top[MAXN];//top[v]表示v所在的重链的顶端节点
int fa[MAXN]; //父亲节点
int deep[MAXN];//深度
int num[MAXN];//num[v]表示以v为根的子树的节点数
int p[MAXN];//p[v]表示v与其父亲节点的连边在线段树中的位置
int fp[MAXN];//和p数组相反
int son[MAXN];//重儿子
int pos;
void init(){
tot = 0;
memset(head,-1,sizeof(head));
pos = 0;
memset(son,-1,sizeof(son));
}
void addedge(int u,int v){
edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}
void dfs1(int u,int v,int d){
deep[v]=d;
fa[v]=u;
num[v]=1;
for(int i=head[v];i!=-1;i=edge[i].next){
int to=edge[i].to;
if(to==u)continue;
dfs1(v,to,d+1);
num[v]+=num[to];
if(son[v]==-1||num[son[v]]<num[to])son[v]=to;
}
}
void dfs2(int u,int v){
top[u]=v;
p[u]=pos++;
if(son[u]==-1)return;
dfs2(son[u],v);
for(int i=head[u];i!=-1;i=edge[i].next){
int to=edge[i].to;
if(to==fa[u]||to==son[u])continue;
dfs2(to,to);
}
}
//线段树
struct Node{
int l,r;
int Max;
int Min;
int ne;
}tr[MAXN*3];
void build(int i,int l,int r){
tr[i].l = l;
tr[i].r = r;
tr[i].Max = 0;
tr[i].Min = 0;
tr[i].ne = 0;
if(l == r)return;
int mid = (l+r)/2;
build(i<<1,l,mid);
build((i<<1)|1,mid+1,r);
}
void push_up(int i)
{
tr[i].Max = max(tr[i<<1].Max,tr[(i<<1)|1].Max);
tr[i].Min = min(tr[i<<1].Min,tr[(i<<1)|1].Min);
}
void push_down(int i){
if(tr[i].l == tr[i].r)return;
if(tr[i].ne)
{
tr[i<<1].Max = -tr[i<<1].Max;
tr[i<<1].Min = -tr[i<<1].Min;
swap(tr[i<<1].Min,tr[i<<1].Max);
tr[(i<<1)|1].Max = -tr[(i<<1)|1].Max;
tr[(i<<1)|1].Min = -tr[(i<<1)|1].Min;
swap(tr[(i<<1)|1].Max,tr[(i<<1)|1].Min);
tr[i<<1].ne ^= 1;
tr[(i<<1)|1].ne ^= 1;
tr[i].ne = 0;
}
}
void update(int i,int k,int val){ // 更新线段树的第k个值为val
if(tr[i].l == k && tr[i].r == k)
{
tr[i].Max = val;
tr[i].Min = val;
tr[i].ne = 0;
return;
}
push_down(i);
int mid = (tr[i].l + tr[i].r)/2;
if(k <= mid)update(i<<1,k,val);
else update((i<<1)|1,k,val);
push_up(i);
}
void ne_update(int i,int l,int r){
if(tr[i].l==l&&tr[i].r==r){
tr[i].Max=-tr[i].Max;tr[i].Min=-tr[i].Min;
swap(tr[i].Max,tr[i].Min);
tr[i].ne^=1;return;
}
push_down(i);
int mid=(tr[i].l+tr[i].r)>>1;
if(r<=mid)ne_update(i<<1,l,r);
else if(l>mid)ne_update((i<<1)|1,l,r);
else ne_update(i<<1,l,mid),ne_update((i<<1)|1,mid+1,r);
tr[i].Min=min(tr[i<<1].Min,tr[(i<<1)|1].Min);
tr[i].Max=max(tr[i<<1].Max,tr[(i<<1)|1].Max);
}
int query(int i,int l,int r){ //查询线段树中[l,r] 的最大值
if(tr[i].l == l && tr[i].r == r)
return tr[i].Max;
push_down(i);
int mid = (tr[i].l + tr[i].r)/2;
if(r <= mid)return query(i<<1,l,r);
else if(l > mid)return query((i<<1)|1,l,r);
else return max(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));
push_up(i);
}
int findmax(int u,int v){//查询u->v边的最大值
int f1 = top[u], f2 = top[v];
int tmp = -100000000;
while(f1 != f2)
{
if(deep[f1] < deep[f2])
{
swap(f1,f2);
swap(u,v);
}
tmp = max(tmp,query(1,p[f1],p[u]));
u = fa[f1]; f1 = top[u];
}
if(u == v)return tmp;
if(deep[u] > deep[v]) swap(u,v);
return max(tmp,query(1,p[son[u]],p[v]));
}
void Negate(int u,int v){
int f1=top[u],f2=top[v];
while(f1!=f2){
if(deep[f1]<deep[f2])swap(f1,f2),swap(u,v);
ne_update(1,p[f1],p[u]);
u=fa[f1];f1=top[u];
}
if(u==v)return;
if(deep[u]>deep[v])swap(u,v);
ne_update(1,p[son[u]],p[v]);
return;
}
int E[MAXN][3];
int main()
{
//freopen("Cola.txt","r",stdin);
freopen("maintaintree.in","r",stdin);
freopen("maintaintree.out","w",stdout);
int T,n;
T=1;
while(T--){
init();
scanf("%d",&n);
for(int i=0;i<n-1;i++){
scanf("%d%d%d",&E[i][0],&E[i][1],&E[i][2]);
addedge(E[i][0],E[i][1]);
addedge(E[i][1],E[i][0]);
}
dfs1(0,1,0);
dfs2(1,1);
build(1,0,pos-1);
for(int i=0;i<n-1;i++){
if(deep[E[i][0]]>deep[E[i][1]])swap(E[i][0],E[i][1]);
update(1,p[E[i][1]],E[i][2]);
}
char ch[10];
int u,v;
while(1){
scanf("%s",ch);
if(ch[0]==‘D‘)break;
scanf("%d%d",&u,&v);
if(ch[0]==‘Q‘)printf("%d\n",findmax(u,v));
else if(ch[0]==‘C‘)update(1,p[E[u-1][1]],v);
else Negate(u,v);
}
}
return 0;
}
主席树
查询区间第k小
Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
const int maxnn=10000000;
int root[maxn],ls[maxnn],rs[maxnn],cnt[maxnn],tot;
int sz[maxn],hash[maxn];
void build(int cur,int l,int r)
{
cur=tot++;
cnt[cur]=0;
if(l!=r)
{
int mid=(l+r)/2;
build(ls[cur],l,mid);
build(rs[cur],mid+1,r);
}
}
void update(int pre,int ps,int &cur,int l,int r)
{
cur=tot++;
cnt[cur]=cnt[pre]+1;
ls[cur]=ls[pre];rs[cur]=rs[pre];
if(l==r)return ;
int mid=(l+r)/2;
if(ps<=mid)update(ls[pre],ps,ls[cur],l,mid);
else update(rs[pre],ps,rs[cur],mid+1,r);
}
int query(int lt,int rt,int l,int r,int k)
{
if(l==r)return l;
int mid=(l+r)/2,cha=cnt[ls[rt]]-cnt[ls[lt]];
if(k<=cha)return query(ls[lt],ls[rt],l,mid,k);
else return query(rs[lt],rs[rt],mid+1,r,k-cha);
}
int main()
{
int m,n,l,r,k;
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;++i)
{
scanf("%d",sz+i);
hash[i]=sz[i];
}
sort(hash+1,hash+n+1);
int siz=unique(hash+1,hash+1+n)-hash-1;
for(int i=1;i<=n;++i)
sz[i]=lower_bound(hash+1,hash+1+siz,sz[i])-hash;
tot=0;
build(root[0],1,siz);
for(int i=1;i<=n;++i)
update(root[i-1],sz[i],root[i],1,siz);
while(m--)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",hash[query(root[l-1],root[r],1,siz,k)]);
}
}
return 0;
}
字典树Trie树
1、查询是否出现
/*
trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母
trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define maxn 2000010
using namespace std;
int tot=1,n;
int trie[maxn][26];
//bool isw[maxn];查询整个单词用
void insert(char *s,int rt)
{
for(int i=0;s[i];i++)
{
int x=s[i]-‘a‘;
if(trie[rt][x]==0)//现在插入的字母在之前同一节点处未出现过
{
trie[rt][x]=++tot;//字母插入一个新的位置，否则不做处理
}
rt=trie[rt][x];//为下个字母的插入做准备
}
/*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/
}
bool find(char *s,int rt)
{
for(int i=0;s[i];i++)
{
int x=s[i]-‘a‘;
if(trie[rt][x]==0)return false;//以rt为头结点的x字母不存在，返回0
rt=trie[rt][x];//为查询下个字母做准备
}
return true;
//查询整个单词时，应该return isw[rt]
}
char s[22];
int main()
{
tot=0;
int rt=1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
insert(s,rt);
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
if(find(s,rt))printf("YES\n");
else printf("NO\n");
}
return 0;
}
2、查询前缀出现次数
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int trie[400001][26],len,root,tot,sum[400001];
bool p;
int n,m;
char s[11];
void insert()
{
len=strlen(s);
root=0;
for(int i=0;i<len;i++)
{
int id=s[i]-‘a‘;
if(!trie[root][id]) trie[root][id]=++tot;
sum[trie[root][id]]++;//前缀后移一个位置保存
root=trie[root][id];
}
}
int search()
{
root=0;
len=strlen(s);
for(int i=0;i<len;i++)
{
int id=s[i]-‘a‘;
if(!trie[root][id]) return 0;
root=trie[root][id];
}//root经过此循环后变成前缀最后一个字母所在位置的后一个位置
return sum[root];//因为前缀后移了一个保存，所以此时的sum[root]就是要求的前缀出现的次数
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>s;
insert();
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
cin>s;
printf("%d\n",search());
}
}
加权并查集
题目大意：
有块积木，开始时它们都属于不同的集合。
然后输入p，表示有p个操作。每个操作都有一个t，如果t==M，那么输入x，y，把x所在集合的所有积木，都堆到y所在集合的上面；如果t==C，那么输入x，查询并输出x下面有多少个积木（不包括x本身）。
解题思路：加权并查集
先设2个数组，under[i]=j表示在积木i下面有j个积木；tot[i]=j表示i所在集合一共有j个积木。
由此可以看出，如果我们要把x摞到y的上面，
在合并操作时，x的下面多了y所在集合的全体，所以under[x]=under[x]+tot[y]；x的father指向y，y所代表的集合总数多了x所在集合的全体，所以tot[y]=tot[x]+tot[y]
上面还更新了tot[x]=0，这个在代码中更不更新无所谓，并查集合并操作合并祖先节点，x的father指向了y，x不会再作为祖先节点出现
在查询祖先节点时，我们需要维护under[]
在路径压缩中更新under时，要先记录下i的祖先节点，在递归回溯时先加上i原父节点的under，再把i的父节点更新为祖先节点。
#include<cstdio>
#include<iostream>
using namespacestd;
intp,father_x,father_y;
char c;
int x,y,un;
intunder[30001],tot[30001],fa[30001];//under:下面有几个积木 tot：集合一共有几个积木
int find(int i)
{
//先更新under再路径压缩
if(fa[i]!=i)
{
int tmp=find(fa[i]);
under[i]+=under[fa[i]];
fa[i]=tmp;
}
return fa[i];
}
void unionn()//x摞到y的上面
{
under[father_x]+=tot[father_y];
tot[father_y]+=tot[father_x];
fa[father_x]=father_y;
}
int main()
{
scanf("%d",&p);
for(int i=0;i<=30000;i++)tot[i]=1,fa[i]=i;
while(p--)
{
cin>>c;
if(c==‘M‘)
{
scanf("%d%d",&x,&y);
father_y=find(y);
father_x=find(x);
if(father_x!=father_y)
unionn();
}
else
{
scanf("%d",&x);
find(x);
printf("%d\n",under[x]);
}
}
}
二分图
二分图匹配可以分4种类型
最大匹配数：最大匹配的匹配边的数目
最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
最大独立数：选取最多的点，使任意所选两点均不相连
最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
定理1：最大匹配数 = 最小点覆盖数（这是 Konig 定理）
定理2：最大匹配数 = 最大独立数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数
1.最大匹配数
最大匹配的匹配边的数目
洛谷P3386 【模板】二分图匹配
P3386 【模板】二分图匹配
题目背景
二分图
题目描述
给定一个二分图，结点个数分别为n,m，边数为e，求二分图最大匹配数
输入输出格式
输入格式：
第一行，n,m,e
第二至e+1行，每行两个正整数u,v，表示u,v有一条连边
输出格式：
共一行，二分图最大匹配
输入输出样例
输入样例#1：
1 1 1
1 1
输出样例#1：
1
说明
n,m<=1000，1<=u<=n，1<=v<=m
因为数据有坑，可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。
算法：二分图匹配
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
intn,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;
int dfs(int x){
for(int i=1;i<=m;i++)
if(vis[i]==0&&re[x][i]){
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;return 1;
}
}
return 0;
}
int main(){
scanf("%d%d%d",&n,&m,&e);
int x,y;
for(int i=1;i<=e;i++){
scanf("%d%d",&x,&y);
re[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d",ans);
}
2.最小点覆盖数
选取最少的点，使任意一条边至少有一个端点被选择
有定理在，判断出一个题可以用最小点覆盖数求的时候，就直接用求最大匹配数的代码搞
poj3041Asteroids
跟上一个题按同一个套路来
题意：给出一个n*n的矩阵和矩阵上m个点，问你最少删除了多少行或列之后，点能全部消失。（联想：给出一张图上的m条边的n个相交顶点(xi, yi)，问最少用其中的几个点，就可以和所有的边相关联）
思路：匈牙利算法的最小覆盖问题：最小覆盖要求在一个二分图上用最少的点（x 或 y 集合的都行），让每条连接两个点集的边都至少和其中一个点关联。根据konig定理：二分图的最小顶点覆盖数等于最大匹配数。理解到这里，将(x,y)这一点，转化为x_y的一条边，把x = a的这一边，转化为(a)这一点，剩下的就是基础的匈牙利算法实现了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 501
#define maxm 10010
intn,k,num,head[maxm],link[maxn],vis[maxn];
struct node{
int to,pre;
}e[maxm];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
int dfs(int x){
for(int i=head[x];i;i=e[i].pre){
int v=e[i].to;
if(vis[v]==0){
vis[v]=1;
if(link[v]==0||dfs(link[v])){
link[v]=x;return 1;
}
}
}
return 0;
}
int main(){
scanf("%d%d",&n,&k);int x,y;
for(int i=1;i<=k;i++){
scanf("%d%d",&x,&y);
Insert(x,y);
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d",ans);
}
3.最大独立数
选取最多的点，使任意所选两点均不相连
poj 1466 Girls and Boys
二分图的最大独立集
因为没有给出具体的男生和女生，所以可以将数据扩大一倍，即n个男生，n个女生，
根据定理，最大独立集=总数-匹配数（本题应该除以2）
给出一系列男女配对意愿信息。求一个集合中的最大人数，满足这个集合中两两的人不能配对。
Sample Input
7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
Sample Output
5
2
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 510
using namespace std;
int link[maxn],vis[maxn],map[maxn][maxn],n;
int dfs(int x){
for(int i=1;i<=n;i++){
if(vis[i]==0&&map[x][i]){
vis[i]=1;
if(link[i]==0||dfs(link[i])){
link[i]=x;
return 1;
}
}
}return 0;
}
int main(){
freopen("1.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
memset(map,0,sizeof(map));
memset(link,0,sizeof(link));
for(int i=1;i<=n;i++){
int u,w,v;
scanf("%d: (%d)",&u,&w);u++;
for(int j=1;j<=w;j++){
scanf("%d",&v);v++;
map[u][v]=map[v][u]=1;
}
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",n-ans/2);
}
}
4.最小路径覆盖数
对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。
hdu 4160Dolls
【题意】
n个箱子
下面n行 a b c 表示箱子的长宽高
箱子可以嵌套，里面的箱子三维都要小于外面的箱子
问：露在外头的箱子有几个
【思路】
只要成功匹配一条边，就等价于成功嵌套一个箱子，就是匹配一条边，露在外面的箱子就少一个
结果就是 n - 最大匹配数
注意一个条件：箱子不可旋转，即长对应长， 宽对应宽
然后就是一个裸的二分匹配
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1010
#define maxm 250010
intn,head[maxn],num,one[maxn],two[maxn],three[maxn],link[maxn];
bool vis[maxn];
struct node{
int pre,to;
}e[maxm];
void Insert(int from,int to){
e[++num].to=to;
e[num].pre=head[from];
head[from]=num;
}
int dfs(int x){
for(int i=head[x];i;i=e[i].pre){
int v=e[i].to;
if(vis[v]==0){
vis[v]=1;
if(link[v]==0||dfs(link[v])){
link[v]=x;return 1;
}
}
}
return 0;
}
int main(){
while(~scanf("%d",&n),n){
if(n==0)return 0;
memset(link,0,sizeof(link));
memset(e,0,sizeof(e));
memset(head,0,sizeof(head));
int sum=0;num=0;
for(inti=1;i<=n;i++)scanf("%d%d%d",&one[i],&two[i],&three[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(one[i]<one[j]&&two[i]<two[j]&&three[i]<three[j])
Insert(i,j+n);
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))sum++;
}
printf("%d\n",n-sum);
}
}
数据结构板子