acm基础算法.docxVIP

/*//树的最小支配集模板。//树的最小点覆盖（二分法）/*最近公共祖先模板/*最小生成树prim算法。/*//hdu 2063二分图最大匹配匈牙利算法。*dijkstra最短路算法。*bellman ford最短路算法。/*最短路之floyd算法模板。奔小康赚大钱(二分最佳匹配)km算法(n表示个人让后n个人对n房子出的钱)//poj1094经典的拓扑排序题。//hdu 3605匈牙利算法二分多重匹配。//hdu2389完全是匈牙利算法bfs的模板。/*网络流最大网络流dinic算法hdu 1532 网络最大流Edmonds Karp算法。网络最大流ford fulkerson基础题。最长上升子序列。最小生成树。基本最小生成树kruskal。强联通经典tarjan算法。tarjan算法判断是不是强联通图！最长公共子序列。动态规划。最长上升公共子序列。完全背包AC自动机线段树区间更新。字典树//树状数组//线段树点更新01背包。Kmp二分图：最小顶点覆盖等于最大匹配；最大独立点集=节点数-最大匹配；/*//树的最小支配集模板。51 35 24 33 5*/#include stdio.h#include math.h#include string.h#include iostreamusing namespace std;#define N 20010struct node{ int to,next;}edge[2*N];int cnt,pre[N];int n;int mark[N];int f[N];int g[N];int num;void add_edge(int u,int v){ edge[cnt].to=v; edge[cnt].next=pre[u]; pre[u]=cnt++;}void DFS(int s){ mark[s]=1; g[num++]=s; for(int p=pre[s];p!=-1;p=edge[p].next) { int v=edge[p].to; if(mark[v]==0) { f[v]=s; DFS(v); } }}int greedy(){ int set[N]; memset(set,0,sizeof(set)); memset(mark,0,sizeof(mark)); int sum=0; for(int i=num-1;i=0;i--) { int k=g[i]; if(mark[k]==0) { if(set[f[k]]==0) { set[f[k]]=1; sum++; } mark[k]=1; mark[f[k]]=1; mark[f[f[k]]]=1; } } return sum;}int main(){ while(scanf(%d,n)(n!=-1)) { if(n==0) continue; cnt=0; num=0; memset(pre,-1,sizeof(pre)); memset(f,0,sizeof(f)); for(int i=1;in;i++) { int x,y; scanf(%d%d,x,y); add_edge(x,y); add_edge(y,x); } f[1]=1; memset(mark,0,sizeof(mark)); DFS(1); printf(%d\n,greedy()); } return 0;}//树的最小点覆盖（二分法）/*40:(1) 11:(2) 2 32:(0)3:(0)53:(3) 1 4 21:(1) 02:(0)0:(0)4:(0)*/#include cstdio#include cstring#include vector#include map#include algorithm#include iostreamusing namespace std;const int maxn=1510;int n;int pre[maxn],vis[maxn];vectorinte[maxn];mapint,intv1,v2;int find(int u)//判断是否存在增广路经，匈牙利算法{ int i,j,k,v; for(i=0;ie[u].size();i++) { v=e[u][i]; if(!vis[v]) { vis[v]=1; if(pre[v]==-1||find(pre[v])) { pre[v]=u; return 1; } } } return 0;}int main(){ while(scanf(%d,n)!=EOF) { int i,j,k,a,b,c,m; v1.clear(); v2.clear(); for(i=0;in;i++) e[i].clear(); for(i