【www.9778.com】数据结构板子

报表难题

 

最小生成树问题,可用Prim算法,也可用Kruskal算法

图论算法模板整理及思路 不断更新 绝对精品,图论不断更新

DFS

www.9778.com 1 1
#include<iostream> 2 #include<queue> 3
#include<cstdio> 4 using namespace std; 5 queue<int>q; 6
int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)
10 { 11 q.push(p); 12 vis[p]=1; 13
printf(“%c–>”,char(q.front()+64)); 14 while(q.size()!=0) 15 { 16 int
k=q.front(); 17 q.pop(); 18 for(int i=1;i<=n;i++) 19 { 20 21
if(vis[i]==0&&map[k][i]==1) 22 { 23 printf(“%c–>”,char(i+64));
24 //q.pop(); 25 q.push(i); 26 vis[i]=1; 27 } 28 } 29 } 30 } 31 int
main() 32 { 33 34 scanf(“%d%d”,&n,&m); 35 for(int i=1;i<=m;i++) 36 {
37 char x,y; 38 //scanf(“n%d %d”,&x,&y); 39 cin>>x>>y; 40
x=x-64; 41 y=y-64; 42 map[x][y]=map[y][x]=1; 43 } 44 bfs(1); 45
return 0; 46 } DFS

BFS

www.9778.com 2 1
#include<iostream> 2 #include<queue> 3
#include<cstdio> 4 using namespace std; 5 queue<int>q; 6
int map[1001][1001]; 7 int vis[1001]; 8 int n,m; 9 void bfs(int p)
10 { 11 q.push(p); 12 vis[p]=1; 13
printf(“%c–>”,char(q.front()+64)); 14 while(q.size()!=0) 15 { 16 int
k=q.front(); 17 q.pop(); 18 for(int i=1;i<=n;i++) 19 { 20 21
if(vis[i]==0&&map[k][i]==1) 22 { 23 printf(“%c–>”,char(i+64));
24 //q.pop(); 25 q.push(i); 26 vis[i]=1; 27 } 28 } 29 } 30 } 31 int
main() 32 { 33 34 scanf(“%d%d”,&n,&m); 35 for(int i=1;i<=m;i++) 36 {
37 char x,y; 38 //scanf(“n%d %d”,&x,&y); 39 cin>>x>>y; 40
x=x-64; 41 y=y-64; 42 map[x][y]=map[y][x]=1; 43 } 44 bfs(1); 45
return 0; 46 } BFS

Flyoed

思路:三层循环遍历中间节点

www.9778.com 3 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 int a[101][101]; 6
int pass[101][101]; 7 int main() 8 { 9 memset(a,999999,sizeof(a));
10 int n,m; 11 scanf(“%d%d”,&n,&m); 12 for(int i=1;i<=m;i++) 13 { 14
int x,y,zhi; 15 scanf(“%d%d%d”,&x,&y,&zhi); 16 a[x][y]=zhi; 17
a[y][x]=zhi; 18 } 19 for(int k=1;k<=n;k++) 20 { 21 for(int
i=1;i<=n;i++) 22 { 23 for(int j=1;j<=n;j++) 24 { 25
if(a[i][j]>a[i][k]+a[k][j]) 26 { 27
a[i][j]=a[i][k]+a[k][j]; 28 pass[i][j]=k; 29 } 30 } 31 }
32 } 33 printf(“%d %dn”,a[1][4],a[2][6]); 34 printf(“%d
%dn”,pass[1][4],pass[2][6]); 35 return 0; 36 } Flyoed

Dijkstra

主要思想:每次找到一个能到达的最近的点,来更新到达其他点的距离

思路:

1.需要一个dis数组记录需要求的点到其他点的最短路径 pre数组记录前驱

2.(1)初始化:dis[]=∞   dis[开始的点]=0  pre[开始的点]=0

 (2)<1>for(int i=1;i<=顶点总数;i++)

      找到dis[i]最小的点

      vis[找到的点]=1

      for(与找到的点相连的点)

      if(dis[find]+w[find][i]<dis[i])

      {

        1.松弛

        2.pre[i]=find 记录前驱

      }

end

www.9778.com 4 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 int a[101][101]; 6
int dis[101]; 7 int maxn=0x7f; 8 int vis[1001]; 9 int pass[1001];
10 void print(int bg,int ed) 11 { 12 int ans[101]; 13 int now=1; 14
ans[now]=ed; 15 now++; 16 // ans[now]=ed; 17 //now++; 18 int
tmp=pass[ed]; 19 while(tmp!=bg) 20 { 21 ans[now]=tmp; 22 now++; 23
tmp=pass[tmp]; 24 } 25 ans[now]=bg; 26 for(int i=now;i>=1;i–) 27
{ 28 if(i!=1) 29 printf(“%d–>”,ans[i]); 30 else 31
printf(“%d”,ans[i]); 32 } 33 } 34 int main() 35 { 36
memset(a,maxn,sizeof(a)); 37 int n,m; 38 int beginn=1; 39
scanf(“%d%d”,&n,&m); 40 for(int i=1;i<=m;i++) 41 { 42 int x,y,zhi; 43
scanf(“%d%d%d”,&x,&y,&zhi); 44 a[x][y]=zhi; 45 a[y][x]=zhi; 46 }
47 48 for(int i=1;i<=n;i++) 49 { 50 if(a[beginn][i]!=maxn) 51 {
52 dis[i]=a[beginn][i]; 53 } 54 } 55 dis[beginn]=0; 56 for(int
i=1;i<=n;i++) 57 { 58 int minn=maxn; 59 int k=-1; 60 for(int
j=1;j<=n;j++) 61 { 62 if(dis[j]<=minn&&vis[j]==0) 63 { 64
minn=dis[j]【www.9778.com】数据结构板子。; 65 k=j; 66 } 67 } 68 vis[k]=1; 69 for(int
j=1;j<=n;j++) 70 { 71 if(dis[k]+a[k][j]<=dis[j]) 72 { 73
dis[j]=dis[k]+a[k][j]; 74 pass[j]=k; 75 } 76 } 77 } 78 for(int
i=1;i<=n;i++) 79 { 80 cout<<dis[i]<<” “; 81
if(i==1)cout<<i; 82 else 83 print(1,i); 84 cout<<endl; 85 }
86 87 return 0; 88 } Dijkstra

SPFA

主要思想:初始时将起点加入队列。每次从队列中取出一个元素,并对所有与它相邻的点进行修改,若某个相邻的点修改成功,则将其入队。直到队列为空时结束

思路:需要变量:

    1.需要一个dis数组记录需要求的点到其他点的最短路径

   2.pre数组记录前驱

   3.queue队列

   4.vis数组  记录该点是否在队列中

  begin

  1.初始化:dis[]=∞   dis[开始的点]=0  pre[开始的点]=0

  2.while(队列不为空)

   (1)取出顶点  vis[顶点]=false

   (2)for(与顶点相连的点)

      if(dis[find]+w[find][i]<dis[i])

      {
        1.松弛

        if(i不在队列中)

        {

          加入队列

          vis[i]=true;

        }           

      }

end;

www.9778.com 5 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<queue> 5 using namespace std;
6 int map[101][101]; 7 int dis[101]; 8 bool vis[101]; 9
queue<int>q; 10 int n,m; 11 int bg=1; 12 void spfa() 13 { 14
dis[bg]=0; 15 vis[bg]=1; 16 q.push(bg); 17 dis[bg]=0; 18 do 19 {
20 int k=q.front(); 21 for(int j=1;j<=n;j++) 22 { 23
if(dis[j]>dis[k]+map[k][j]) 24 { 25
dis[j]=dis[k]+map[k][j]; 26 if(vis[j]==0) 27 { 28 q.push(j);
29 vis[j]=1; 30 } 31 } 32 } 33 q.pop(); 34 vis[k]=0; 35
}while(q.size()!=0); 36 for(int i=1;i<=n;i++) 37
cout<<dis[i]<<endl; 38 } 39 int main() 40 { 41
memset(map,0x7f,sizeof(map)); 42 memset(dis,0x7f,sizeof(dis)); 43
memset(vis,0,sizeof(vis)); 44 scanf(“%d%d”,&n,&m); 45 for(int
i=1;i<=m;i++) 46 { 47 int x,y,z; 48 scanf(“%d%d%d”,&x,&y,&z); 49
map[x][y]=map[y][x]=z; 50 } 51 //int a,b; 52
//scanf(“%d%d”,&a,&b); 53 spfa(); 54 return 0; 55 } SPFA邻接矩阵存储  
www.9778.com 6 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 #include<queue> 5 using namespace std;
6 const int MAXN=30001; 7 const int maxn=0x7fffffff; 8 struct node 9 {
10 int u; 11 int v; 12 int w; 13 int next; 14 }edge[MAXN]; 15 int
num=1; 16 int head[MAXN]; 17 int n,m,begin,end; 18 int dis[MAXN]; 19
int vis[MAXN]; 20 void spfa() 21 { 22 for(int
i=1;i<=n;i++)dis[i]=maxn; 23 queue<int>q; 24 vis[begin]=1;
25 q.push(begin); 26 dis[begin]=0; 27 while(q.size()!=0) 28 { 29 int
p=q.front(); 30 q.pop(); 31 vis[p]=0; 32 for(int
i=head[p];i!=-1;i=edge[i].next) 33 { 34
if(dis[edge[i].v]>dis[p]+edge[i].w&&dis[p]!=maxn) 35 { 36
dis[edge[i].v]=dis[p]+edge[i].w; 37 if(vis[edge[i].v]==0) 38
{ 39 q.push(edge[i].v); 40 vis[edge[i].v]=1; 41 } 42 } 43 } 44 }
45 printf(“%d”,dis[end]); 46 } 47 int main() 48 { 49
scanf(“%d%d%d%d”,&n,&m,&begin,&end); 50 for(int
i=1;i<=n;i++)head[i]=-1; 51 for(int i=1;i<=m;i++) 52 { 53
scanf(“%d%d%d”,&edge[num].u,&edge[num].v,&edge[num].w); 54
edge[num].next=head[edge[num].u]; 55 head[edge[num].u]=num++;
56 edge[num].w=edge[num-1].w; 57 edge[num].u=edge[num-1].v; 58
edge[num].v=edge[num-1].u; 59
edge[num].next=head[edge[num].u]; 60 head[edge[num].u]=num++;
61 } 62 spfa(); 63 return 0; 64 } SPFA邻接表存储

 

 

单源最短路径输出

主要思想

主要利用递归的思想,一层一层的进行迭代

www.9778.com 71 void
print(int x) 2 { 3 if(pre[a][x]==0)return; 4 print(pre[a][x]); 5
cout<<“->”<<x; 6 } 7 //a为开始的点 单源最短路的输出

 Tarjan算法

思路:

基本思路:

1.初始化

2.入栈

3.枚举:

    1.不在队列中->访问,进行赋值,

    2.在队列中->赋值

4.寻找根->输出结果

 

www.9778.com 8 1
#include<cstdio> 2 #include<algorithm> 3
#include<string.h> 4 using namespace std; 5 struct node { 6 int
v,next; 7 } edge[1001]; 8 int DFN[1001],LOW[1001]; 9 int
stack[1001],heads[1001],visit[1001],cnt,tot,index; 10 void add(int
x,int y) { 11 edge[++cnt].next=heads[x]; 12 edge[cnt].v = y; 13
heads[x]=cnt; 14 return ; 15 } 16 void tarjan(int x) {
//代表第几个点在处理。递归的是点。 17 DFN[x]=LOW[x]=++tot;//
新进点的初始化。 18 stack[++index]=x;//进站 19
visit[x]=1;//表示在栈里 20 for(int i=heads[x]; i!=-1;
i=edge[i].next) { 21 if(!DFN[edge[i].v]) { 22 //如果没访问过 23
tarjan(edge[i].v);//往下进行延伸,开始递归 24
LOW[x]=min(LOW[x],LOW[edge[i].v]);//递归出来,比较谁是谁的儿子/父亲,就是树的对应关系,涉及到强连通分量子树最小根的事情。
25 } else if(visit[edge[i].v ]) { 26 //如果访问过,并且还在栈里。 27
LOW[x]=min(LOW[x],DFN[edge[i].v]);//比较谁是谁的儿子/父亲。就是链接对应关系
28 } 29 } 30 if(LOW[x]==DFN[x]) {
//发现是整个强连通分量子树里的最小根。 31 do { 32 printf(“%d
“,stack[index]); 33 visit[stack[index]]=0; 34 index–; 35 }
while(x!=stack[index+1]);//出栈,并且输出。 36 printf(“n”); 37 } 38
return ; 39 } 40 int main() { 41 memset(heads,-1,sizeof(heads)); 42 int
n,m; 43 scanf(“%d%d”,&n,&m); 44 int x,y; 45 for(int i=1; i<=m; i++) {
46 scanf(“%d%d”,&x,&y); 47 add(x,y); 48 } 49 for(int i=1; i<=n; i++)
50 if(!DFN[i])
tarjan(1);//当这个点没有访问过,就从此点开始。防止图没走完 51 return 0;
52 } Tarjan

 Kruskal算法

主要思想:

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。   思路: 算法描述:
1.初始化并查集。father[x]=x。 2.tot=0
3.将所有边用快排从小到大排序。sort 4.计数器 k=0; 5.for (i=1; i<=M;
i++)      //循环所有已从小到大排序的边   if 
这是一条u,v不属于同一集合的边(u,v)(因为已经排序,所以必为最小),    
begin      ①合并u,v所在的集合,相当于把边(u,v)加入最小生成树。      ②tot=tot+W(u,v)       ③k++      
④如果k=n-1,说明最小生成树已经生成,则break;     end; 6.
结束,tot即为最小生成树的总权值之和。  
www.9778.com 9 1
#include<iostream> 2 #include<cstdio> 3
#include<cstring> 4 using namespace std; 5 int map[101][101];
6 int nmap[101][101]; 7 int pass[101]; 8 int vis[101]; 9 int
now=1; 10 int n,m; 11 int num=0; 12 void dfs(int p) 13 { 14 vis[p]=1;
15 for(int i=1;i<=n;i++) 16 { 17 if(vis[i]==0&&map[p][i]==1) 18
{ 19 dfs(i); 20 21 } 22 } 23 pass[now]=p; 24 now++; 25 } 26 void
ndfs(int p) 27 { 28 vis[p]=0; 29 for(int i=1;i<=n;i++) 30 { 31
if(vis[i]==1&&nmap[p][i]==1) 32 ndfs(i); 33 } 34 } 35 int main()
36 { 37 38 scanf(“%d%d”,&n,&m); 39 for(int i=1;i<=m;i++) 40 { 41 int
x,y; 42 scanf(“%d%d”,&x,&y); 43 map[x][y]=1; 44 nmap[y][x]=1; 45
} 46 for(int i=1;i<=n;i++) 47 { 48 if(vis[i]==0) 49 dfs(i); 50 } 51
pass[now]=1; 52 for(int i=n;i>=1;i–) 53 { 54
if(vis[pass[i]]==1) 55 { 56 ndfs(pass[i]); 57 num++; 58 } 59 } 60
cout<<num; 61 return 0; 62 } Kruskal

 

   

 

 

Kruskal算法将一个连通块当做一个集合。Kruskal首先将所有的边按从小到大顺序排序(一般使用快排),并认为每一个点都是孤立的,分属于n个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合,那么就把这条边加入最小生成树,这两个不同的集合就合并成了一个集合;如果这条边连接的两个点属于同一集合,就跳过。直到选取了n-1条边为止。

不断更新
绝对精品,图论不断更新 DFS 1 #includeiostream 2 #includequeue 3
#includecstdio 4 using namespace std; 5 queue int q; 6 int…

问题描述:给出n个数,求相邻两个数绝对值之差的最小值。有两种操作,一种是Q(表示你需要回答目前这些数的相邻两个数绝对值之差的最小值),一种是k(表示删原第K个数)。

树状数组

(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(“%dn”,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);

}

Prim算法是基于顶点来实现最小生成树,Kruskal算法是基于边来实现最小生成树

文件输入:n,m(n,m<=100000)

线段树

线段树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(“%dn”,ans);

        }

        else

        {

             scanf(“%d%d%d”,&a,&b,&y);//区间修改

             change_interval(1);

        }

    }

}

Prime算法,用java写的

      n个数

树链剖分

【题目描述】

给你由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(“%dn”,findmax(u,v));

            else if(ch[0]==’C’)update(1,p[E[u-1][1]],v);

            else Negate(u,v);

        }

    }

    return 0;

}

[java]  import java.util.Scanner; 
//无穷大量  
class MAX 

    static int num=0x3f3f3f3f; 

class prime{ 
    int n; 
    int[][] map=new int[105][105]; 
    int[] dis=new int[105]; 
    int[] visit=new int[105]; 
    public void init(int[][] a,int m) 
    { 
        n=m; 
        for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) 
        { 
            map[i][j]=a[i][j]; 
        } 
        for(int i=1;i<=n;i++) 
        visit[i]=0; 
        visit[1]=1; 
        for(int i=1;i<=n;i++) 
        dis[i]=map[1][i]; 
        dis[1]=0; 
    } 
    public int solve() 
    { 
        int i,j,Min,v,sum=0; 
        //每次加入一个节点  
        for(i=1;i<n;i++) 
        { 
            Min=MAX.num; 
            v=0; 
            for(j=1;j<=n;j++) 
            if(visit[j]==0&&dis[j]<Min) 
            { 
                Min=dis[j]; 
                v=j; 
            } 
            sum+=Min; 
            visit[v]=1; 
            for(j=1;j<=n;j++) 
            if(visit[j]==0&&dis[j]>map[v][j]) 
            dis[j]=map[v][j]; 
        } 
        return sum; 
    } 

public class Main{ 
    public static void main(String args[]) 
    { 
        int nn,m; 
        int[][] mapp=new int[105][105]; 
        Scanner t=new Scanner(System.in); 
        while(true) 
        { 
            //初始化为无穷大  
            for(int i=0;i<105;i++) 
            for(int j=0;j<105;j++) 
            mapp[i][j]=MAX.num; 
            nn=t.nextInt(); 
            if(nn==0) 
            break; 
            m=t.nextInt(); 
            int a,b,c; 
            for(int i=0;i<m;i++) 
            { 
                a=t.nextInt(); 
                b=t.nextInt(); 
                c=t.nextInt(); 
                if(mapp[a][b]>c) 
                mapp[a][b]=mapp[b][a]=c; 
            } 
            prime s=new prime(); 
            s.init(mapp,nn); 
            System.out.println(s.solve()); 
        } 
        t.close(); 
    } 

      以下每行一个共m个操作

主席树

查询区间第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(“%dn”,hash[query(root[l-1],root[r],1,siz,k)]);

        }

    }

    return 0;

}

import java.util.Scanner;
//无穷大量
class MAX
{
 static int num=0x3f3f3f3f;
}
class prime{
 int n;
 int[][] map=new int[105][105];
 int[] dis=new int[105];
 int[] visit=new int[105];
 public void init(int[][] a,int m)
 {
  n=m;
  for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++)
  {
   map[i][j]=a[i][j];
  }
  for(int i=1;i<=n;i++)
  visit[i]=0;
  visit[1]=1;
  for(int i=1;i<=n;i++)
  dis[i]=map[1][i];
  dis[1]=0;
 }
 public int solve()
 {
  int i,j,Min,v,sum=0;
  //每次加入一个节点
  for(i=1;i<n;i++)
  {
   Min=MAX.num;
   v=0;
   for(j=1;j<=n;j++)
   if(visit[j]==0&&dis[j]<Min)
   {
    Min=dis[j];
    v=j;
   }
   sum+=Min;
   visit[v]=1;
   for(j=1;j<=n;j++)
   if(visit[j]==0&&dis[j]>map[v][j])
   dis[j]=map[v][j];
  }
  return sum;
 }
}
public class Main{
 public static void main(String args[])
 {
  int nn,m;
  int[][] mapp=new int[105][105];
  Scanner t=new Scanner(System.in);
  while(true)
  {
   //初始化为无穷大
   for(int i=0;i<105;i++)
   for(int j=0;j<105;j++)
   mapp[i][j]=MAX.num;
   nn=t.nextInt();
   if(nn==0)
   break;
   m=t.nextInt();
   int a,b,c;
   for(int i=0;i<m;i++)
   {
    a=t.nextInt();
    b=t.nextInt();
    c=t.nextInt();
    if(mapp[a][b]>c)
    mapp[a][b]=mapp[b][a]=c;
   }
   prime s=new prime();
   s.init(mapp,nn);
   System.out.println(s.solve());
  }
  t.close();
 }
}

文件输出:对应Q的回答

字典树Trie树

Kruskal算法,用C写的

样例输入:

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(“YESn”);

        else printf(“NOn”);

    }

    return 0;

}

[cpp] #include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
#include<math.h>  
struct bian 

    int x; //起点  
    int y; //终点  
    int len; //距离  
}list[2005]; 
int f[105]; 
int n,m;//n个点,m条边  
int cmp(const void *a,const void *b) 

    return (*(struct bian *)a).len-(*(struct bian *)b).len; 

void init() 

    int i; 
    for(i=1;i<=n;i++) 
    f[i]=i; 

int find(int x) 

    int r=x; 
    while(f[r]!=r) 
    r=f[r]; 
    f[x]=r; 
    return r; 

int Union(int x,int y) 

    int fx,fy; 
    fx=find(x); 
    fy=find(y); 
    if(fx!=fy) 
    { 
        f[fy]=fx; 
        return 1; 
    } 
    return 0; 

int main() 

    int i,t,ans,num; 
    while(scanf(“%d”,&n),n) 
    { 
        scanf(“%d”,&m); 
        t=0; 
        for(i=0;i<m;i++) 
        { 
            scanf(“%d %d
%d”,&list[i].x,&list[i].y,&list[i].len); 
        } 
        qsort(list,m,sizeof(struct bian),cmp); 
        ans=0; 
        num=0; 
        init(); 
        for(i=0;i<m;i++) 
        { 
            if(Union(list[i].x,list[i].y)) 
            { 
                ans+=list[i].len; 
                num++; 
                if(num==n-1) 
                break; 
            } 
            else 
            continue; 
        } 
        printf(“%dn”,ans); 
    } 
    return 0; 

    5 3

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(“%dn”,search());

    }

}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
struct bian
{
 int x; //起点
 int y; //终点
 int len; //距离
}list[2005];
int f[105];
int n,m;//n个点,m条边
int cmp(const void *a,const void *b)
{
 return (*(struct bian *)a).len-(*(struct bian *)b).len;
}
void init()
{
 int i;
 for(i=1;i<=n;i++)
 f[i]=i;
}
int find(int x)
{
 int r=x;
 while(f[r]!=r)
 r=f[r];
 f[x]=r;
 return r;
}
int Union(int x,int y)
{
 int fx,fy;
 fx=find(x);
 fy=find(y);
 if(fx!=fy)
 {
  f[fy]=fx;
  return 1;
 }
 return 0;
}
int main()
{
 int i,t,ans,num;
 while(scanf(“%d”,&n),n)
 {
  scanf(“%d”,&m);
  t=0;
  for(i=0;i<m;i++)
  {
   scanf(“%d %d %d”,&list[i].x,&list[i].y,&list[i].len);
  }
  qsort(list,m,sizeof(struct bian),cmp);
  ans=0;
  num=0;
  init();
  for(i=0;i<m;i++)
  {
   if(Union(list[i].x,list[i].y))
   {
    ans+=list[i].len;
    num++;
    if(num==n-1)
    break;
   }
   else
   continue;
  }
  printf(“%dn”,ans);
 }
 return 0;
}

    1 2 5 8 14

加权并查集

题目大意:
有块积木,开始时它们都属于不同的集合。
然后输入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 namespace std;

int p,father_x,father_y;

char c;

int x,y,un;

int under[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(“%dn”,under[x]);

        }

    }

}

 

    Q

二分图

二分图匹配可以分4种类型

最大匹配数:最大匹配的匹配边的数目

最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择

最大独立数:选取最多的点,使任意所选两点均不相连

最小路径覆盖数:对于一个
DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为
0(即单个点)。

定理1:最大匹配数 = 最小点覆盖数(这是 Konig
定理)

定理2:最大匹配数 = 最大独立数

定理3:最小路径覆盖数 = 顶点数 – 最大匹配数

    K 2

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;

int n,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);

}

    K 3

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

int n,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);

}

    Q

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(“%dn”,n-ans/2);

    }

}

样例输出:

4.最小路径覆盖数

对于一个
DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为
0(即单个点)。

hdu 4160 Dolls

【题意】

n个箱子

下面n行 a b c 表示箱子的长宽高

箱子可以嵌套,里面的箱子三维都要小于外面的箱子

问: 露在外头的箱子有几个

【思路】

只要成功匹配一条边,就等价于成功嵌套一个箱子,就是匹配一条边,露在外面的箱子就少一个

结果就是 n – 最大匹配数

注意一个条件: 箱子不可旋转,即 长对应长, 宽对应宽

 

然后就是一个裸的二分匹配

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 1010

#define maxm 250010

int
n,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(int
i=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(“%dn”,n-sum);

    }

}

 

     1

     6

解法1:

#include
<iostream>

using
namespace std;

 

int
totN, totM, nMin=0x7fffffff;

int
iData[100010], iValue[100010];

 

void
ReadData(void) {

    scanf(“%d%d”,&totN,&totM);

    int i;

    for (i=1;i<=totN;i++)
scanf(“%d”,&iData[i]);

    for (i=1;i<totN;i++) {

        iValue[i] = abs(iData[i+1]

  • iData[i]);

        if (iValue[i] < nMin) nMin
= iValue[i];

    }

    return;

}

 

void
FindMin(void) {

    int i, k(0x7fffffff);

    for (i=1;i<totN;i++)

        if (iValue[i]!=-1)

            if (iValue[i] < k)

                k = iValue[i];

    nMin = k;

    return;

}

   

void
DeleteNum(int pos) {

    int i, j, k, q;

    k = iValue[pos];

    iValue[pos] = -1;

    i = pos-1; while (iValue[i]==-1
&& i>0) i–;

    q = iValue[i];

    j = pos+1; while (iValue[j]==-1
&& j<=totN) j++;

    if (i!=0 && j<=totN) iValue[i]
= abs(iData[j] – iData[i]);

    if (j>totN) iValue[i] =
0x7fffffff;

   

    if (k==nMin || q==nMin ||
iValue[i]<=nMin) FindMin();

   

    return;

}

 

void
Proc() {

    char c; int i, j;

    ReadData();

    for (j=1;j<=totM;j++) {

        do

            scanf(“%c”,&c);

        while
(c!=’Q’&&c!=’k’&&c!=’K’&&c!=’q’);

        if (c==’Q’ || c== ‘q’)

           
printf(“%dn”,nMin);

        else {

            scanf(“%d”,&i);

            DeleteNum(i);

        }

    }

    return ;

}

 

int
main() {

    Proc();

    return 0;

}

解法2:

#include<iostream>

using
namespace std;

 

int
Hash[10000000],pre[100001],next[100001],a[100001];

int
main()

{    

       int N,M,i,k;

       char ch;

       cin>>N>>M;

      

       a[0]=0;

       for(i=1;i<=N;i++)

       {

       scanf(“%d”,a+i);

       pre[i]=i-1;

       next[i]=i+1;

      
Hash[abs(a[i]-a[i-1])]++;

       }

       Hash[a[1]]–;

       int Min=0,temp;

       for(i=1;i<=M;i++)

       {       do

               {

               scanf(“%c”,&ch);

               }while(ch==’
‘||ch==’n’);

               if(ch==’Q’)

               {

                 
while(Hash[Min]==0)Min++;

                         

                 
printf(“%dn”,Min);        

               }

              

               else

               {

                     
scanf(“%d”,&k);   

                    
if(pre[k]!=0)

                    
Hash[abs(a[k]-a[pre[k]])]–;

                    
if(next[k]!=N+1)

                    
Hash[abs(a[k]-a[next[k]])]–;

                    

                    
next[pre[k]]=next[k];

                    
pre[next[k]]=pre[k];

                    

                    
if(pre[k]!=0&&next[k]!=0)

                     {

                    
temp=abs(a[pre[k]]-a[next[k]]);

                    
if(temp<Min)Min=temp;

                    
Hash[temp]++;

                     }

               }              

       }

}

解法3:

#include<iostream>

using
namespace std;

 

struct
data{int v,l,r;}heap[100005];

struct
node{int pre,next,v;}a[100005];

int
num=0,n;

bool
Delete[100005]={0};

void
heapup()

{

     int i=num;

     while(
i>1&&heap[i].v<heap[i/2].v){swap(heap[i],heap[i/2]);i/=2;}

}

void
heapdown(int st)

{

     int i=st,j;

     while( i*2<=num)

     {

            j=i*2;

            if(
heap[j].v>heap[j+1].v&&j<num)j++;

            if(
heap[i].v>heap[j].v){ swap(heap[i],heap[j]);}

            else break;

            j=i;

            }

}

int
main()

{

    int i,next,pre,x,m,p;

    char c;

    cin>>n>>m;

    for(
i=1;i<=n;i++)scanf(“%d”,&a[i].v);

    a[1].pre=0;a[1].next=2;

   
heap[++num].v=abs(a[1].v-a[2].v);

   
heap[num].l=1;heap[num].r=2;

    heapup();

    for( i=2;i<n;i++)

    {

         a[i].pre=i-1;

         a[i].next=i+1;

        
heap[++num].v=abs(a[i].v-a[i+1].v);

        
heap[num].l=i;heap[num].r=i+1;

         heapup();

         }

   
a[n].pre=n-1;a[n].next=0;

    while( m–)

    {

           cin>>c;

           if(c==’Q’)

           {

                     while(
Delete[heap[1].l]||Delete[heap[1].r])

                     {

                           
swap(heap[1],heap[num]);

                           
num–;

                           
heapdown(1);

                            }

                   
printf(“%dn”,heap[1].v);

                     }

           else

           {

                scanf(“%d”,&x);

                pre=a[x].pre;

               
next=a[x].next;

               
a[pre].next=next;

               
a[next].pre=pre;

                if(
pre!=0&&next!=0)

                {

                   
heap[++num].v=abs(a[pre].v-a[next].v);

                   
heap[num].l=pre;

                   
heap[num].r=next;

                    heapup();

                    }

                Delete[x]=1;

                }

           }

     return 0;

}