tem

 最大堆
#define maxn 1000
#define INF 1<<27
int A[maxn];
int heap_size;
//int n;
int PARENT(int i){
  return i/2;
}
int LEFT(int i){
	return i*2;
}
int RIGHT(int i){
	return 2*i+1;
}
void swap(int &a,int &b){
	int temp;
	temp=a;
	a=b;
	b=temp;
}
void MAX_HEAPIFY(int i){
	int l=LEFT(i);
	int r=RIGHT(i);
	int largest;
	if(l<=heap_size&&A[l]>A[i])
		largest=l;	
	else
		largest=i;
	if(r<=heap_size&&A[r]>A[largest])
		largest=r;
	if(largest!=i){
		swap(A[i],A[largest]);
		MAX_HEAPIFY(largest);
	}
}
void BUILD_MAX_HEAP(int n){
	heap_size=n; //n为总元素的个数 heap_size<=n<=maxn
	for(int i=n/2;i>=1;i--){
		MAX_HEAPIFY(i);
	}
}
void HEAPSORT(int n){ //递增的排序
	BUILD_MAX_HEAP(n);
	for(int i=n/2;i>=2;i--){
		swap(A[1],A[i]);
		heap_size--;
		MAX_HEAPIFY(1);
	}
}
int HEAP_MAXIMUM(){
	return A[1];
}
int HEAP_EXTRACT_MAX(){
	if(heap_size<1)
		return -1; //出错
	int max=A[1];
	A[1]=A[heap_size];
	heap_size--;
	MAX_HEAPIFY(1);
	return max;
}
void HEAP_INCREASE_KEY(int i,int key){
	if(key<A[i])
		return ; //出错
	A[i]=key;
	while(i>1&&A[PARENT(i)]<A[i]){
		swap(A[i],A[PARENT(i)]);
		i=PARENT(i);
	}
}
void MAX_HEAP_INSERT(int key){
	heap_size++;
	A[heap_size]=0-INF;
	HEAP_INCREASE_KEY(heap_size,key);
}












  最小生成树
Kruskal
#define maxn 101
#define maxm 10001
int n;//n为点的数量
int m;//m为边的数量
int p[maxn],r[maxn];
int u[maxm],v[maxm],w[maxm];
int find(int x){
	return p[x]==x? x:p[x]=find(p[x]);
}
int Kruskal(){
	int ans=0; //ans存储最小生成树的重量
	for(int i=1;i<=n;i++){
		p[i]=i;  //初始化 并查集
	}
	for(int i=1;i<=n;i++){
		r[i]=i;  //初始化边序号
	}
	sort(r+1,r+1+m);
	for(int i=1;i<=m;i++){
		int e=r[i]; //这个不可以去掉
		int x=find(u[e]);
		int y=find(v[e]);
		if(x!=y){
			ans+=w[e];
			p[x]=y;

		}
	}
	return ans;
}

Prim
#include <iostream>
#include <queue>
using namespace std;
#define maxn 1000
#define maxm 1000*1000
#define INF 1<<28
int n,m;
int first[maxn];
int u[maxm],v[maxm],w[maxm],next1[maxm];

void read_graph(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		first[i]=-1;
	for(int e=1;e<=m;e++){
		cin>>u[e]>>v[e]>>w[e]; //这是有向图
		next1[e]=first[u[e]];
		first[u[e]]=e;
	}
}
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q;
int key[maxn],pi[maxn];
bool inq[maxn];
void prim(int r){
	
	for(int i=1;i<=n;i++){
		key[i]=INF;
		pi[i]=0;
	}
	key[r]=0;
	for(int i=1;i<=n;i++){
		q.push(make_pair(key[i],i));
	}
	memset(inq,true,sizeof(inq));
	while(!q.empty()){
		pii u=q.top();
		q.pop();
		int x=u.second;
		inq[x]=false;
		for(int e=first[x];e!=-1;e=next1[e]){
			if(inq[x]&&w[e]<key[v[e]]){
				pi[v[e]]=x;
				key[v[e]]=w[e];
			}
		}
	}
}






最短路
dijkstra
#include <iostream>
#include <queue>
using namespace std;
#define maxn 1000
#define maxm 1000*1000
#define INF 1<<28
int d[maxn];
bool done[maxn];
int n,m;
int first[maxn];
int u[maxm],v[maxm],w[maxm],next1[maxm];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > q; //最小优先队列
void read_graph(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		first[i]=-1;
	for(int e=1;e<=m;e++){
		cin>>u[e]>>v[e]>>w[e]; //这是有向图
		next1[e]=first[u[e]];
		first[u[e]]=e;
	}
}
void Dijkstra(){
	for(int i=1;i<=n;i++)	
		d[i]=(i==1?0:INF);
	memset(done,0,sizeof(done));
	while(!q.empty())
		q.pop();
	q.push(make_pair(d[1],1));
	while(!q.empty()){
		pii u=q.top();
		q.pop();
		int x=u.second;
		if(done[x])
			continue;
		done[x]=true;
		for(int e=first[x];e!=-1;e=next1[e]){
			if(d[v[e]>d[x]+w[e]]){
				d[v[e]]=d[x]+w[e];
				q.push(make_pair(d[v[e]],v[e]));
			}
		}
	}
}


Floyd
#define maxn 1000
int d[maxn][maxn];
void floyd(int n){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				d[i][j]=d[i][j]<d[i][k]+d[k][j]? d[i][j]:d[i][k]+d[k][j];
			}
		}
	}
}

SPFA
#include <iostream>
#include <queue>
using namespace std;
#define maxn 1000
#define maxm 1000*1000
#define INF 1<<28
int d[maxn];
int n,m;
int first[maxn];
int u[maxm],v[maxm],w[maxm],next1[maxm];

void read_graph(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		first[i]=-1;
	for(int e=1;e<=m;e++){
		cin>>u[e]>>v[e]>>w[e]; //这是有向图
		next1[e]=first[u[e]];
		first[u[e]]=e;
	}
}
queue <int> q;
bool inq[maxn];

void SPFA(int s){
	for(int i=1;i<=n;i++)
		d[i]=(i==s? 0:INF);
	memset(inq,0,sizeof(inq));
	q.push(s);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		inq[x]=false;
		for(int e=first[x];e!=-1;e=next1[e]){
			if(d[x]+w[e]<d[v[e]]){
				d[v[e]]=d[x]+w[e];
				if(!inq[v[e]]){  //如果已经在队列中 就不要重复加了
					inq[v[e]]=true;
					q.push(v[e]);
				}
			}
		}
	}

}


差分约束
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
#define maxn 1003
#define inf 1<<28
int n,m,k; //n点的个数 k边的个数
int d[maxn];
int link[maxn];
//  传统的用SPFA解差分约束..是给出的一组或者说要化成一组 a - b <= k 的形式...然后来构边.. a为终点，b为起点..权值为k...用SPFA求出的是确定一个数后的最大解..  条件为 d[e[m].v]>d[e[m].u]+e[m].w
  //如果是最小解...这里就要更加的深入理解用SPFA解差分约束了.条件为.d[e[m].v]>d[e[m].u]+e[m].w
class _edge{
public:
	int u;
	int v;
	int w;
	int next;
	void make(int u1,int v1,int w1){
		u=u1;
		v=v1;
		w=w1;
		next=link[u1];
		link[u1]=k;
	}
};
_edge e[maxn*maxn];
queue<int> q;
bool spfa(int s){
	bool inq[maxn]; 
	int sum[maxn];
	memset(sum,0,sizeof(sum));  
                memset(inq,false,sizeof(inq)); 
	for(int i=0;i<=n;i++){
		d[i]=inf;
		k++;
		e[k].make(0,i,0);
	}
	while (!q.empty()) 
		q.pop();
	d[s]=0;
	q.push(s);
	int t,m;
	while(!q.empty()){
		t=q.front();
		q.pop();
		inq[t]=false;
		m=link[t];
		while(m){
			if(d[e[m].v]>d[e[m].u]+e[m].w){
				d[e[m].v]=d[e[m].u]+e[m].w;
				if(!inq[e[m].v]){
					q.push(e[m].v);
					sum[e[m].v]++;
					if(sum[e[m].v]>=n+1)   //注意顶点个数为n+1 算上超级节点的话
						return false;
					inq[e[m].v]=true;
				}
			}
			m=e[m].next;
		}
	}
	return true;
}

int main(){
	while(~scanf("%d%d",&n,&m)){
		memset(link,0,sizeof(link));  //要注意这个地方
		char temp;
		int a,b,dis;
		k=0;
		for(int i=1;i<=m;i++){
			temp=getchar();   
            while (temp!='V' && temp!='P' ) temp=getchar(); ;   
			if(temp=='P'){
				//cin>>a>>b>>dis;
				scanf("%d%d%d",&a,&b,&dis);
				k++;
				e[k].make(b,a,dis);	//xi-xj<=w(vj,vi) xi=shortestpath(v0,vi)	
				k++;
				e[k].make(a,b,-dis);
			}
			else{
				//cin>>a>>b;
				scanf("%d%d",&a,&b);
				k++;
				e[k].make(a,b,-1);								
			}
		}
		if(spfa(0)){
			cout<<"Reliable"<<endl;
		}
		else
			cout<<"Unreliable"<<endl;
	}
	return 0;
}










字符串匹配
KMP
#include <iostream>
#include <string>
using namespace std;
string text;
string word;
int pi[ 10009];  //关键词的长度
int n,m;  
void compute_prefix_function(){
	pi[1-1]=0;  
	int k=0;
	for(int q=2;q<=m;q++){
		while(k>0&&word[k]!=word[q-1]){
			k=pi[k-1];
		}
		if(word[k]==word[q-1]){
			k++;
		}
		pi[q-1]=k;
	}
}
int kmp(){
	int tot=0;
	n=text.size();
	m=word.size();
	compute_prefix_function();
	int q=0;
	for(int i=1;i<=n;i++){
		while(q>0&&word[q]!=text[i-1]){
			q=pi[q-1];
		}
		if(word[q]==text[i-1])
			q++;
		if(q==m){
			tot++;
			q=pi[q-1];
		}
		
	}
	return tot;
}

Trie树
#include <iostream>
#include <cstring>
using namespace std;
#define sigma_size 26
#define maxn 9999999
struct Trie{
	int ch[maxn][sigma_size];
	int val[maxn];
	int sz;
	Trie(){
		sz=1;
		memset(ch[0],0,sizeof(ch[0]));
	}
	int idx(char c){
		return c-'a';
	}
	void insert(char *s,int v){
		int u=0;
		int n=strlen(s);
		for(int i=0;i<n;i++){
			int c=idx(s[i]);
			if(!ch[u][c]){
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz]=0; 
				ch[u][c]=sz++;
			}			
			u=ch[u][c];	
			
		}	
		val[u]=v;//若val[u]应经有值 说明 重复
	}
int find(char *s){	
		int u=0;
		int n=strlen(s);
		for(int i=0;i<n;i++){
			int c=idx(s[i]);
			if(!ch[u][c])
				return -1; //节点不存在
			else {
				u=ch[u][c];				
			}
		}
		return val[u];			
	}
};
Trie trie;




int main(){
	int noc;
	cin>>noc;
	while(noc--){
		cin>>word>>text;
		cout<<kmp()<<endl;
	}
	

	return 0;
}

AC自动机
#include <iostream>
#include <queue>

using namespace std;
#define maxn 399999
#define sigma_size 26


    int nok[maxn];
	int ch[maxn][sigma_size];
	int val[maxn];
	int last[maxn];
	int num;
	int cnt[maxn];
	int f[maxn];
	int sz;
	void init(){
		sz=1;
		num=0;
		memset(nok,0,sizeof(nok));
		memset(ch[0],0,sizeof(ch[0]));
		memset(last,0,sizeof(last));
		memset(f,0,sizeof(f));
		memset(cnt,0,sizeof(cnt));
	}
	int idx(char c){
		return c-'a';
	}
	void insert(char *s,int v){		
		int u=0;
		int n=strlen(s);
		for(int i=0;i<n;i++){
			int c=idx(s[i]);			
			if(!ch[u][c]){				
				memset(ch[sz],0,sizeof(ch[sz]));
				val[sz]=0; 
				ch[u][c]=sz++;
				
			}			
			u=ch[u][c];				
		}	
		//val[u]=v;
		if(!val[u]){  // 判断是否重复
			val[u]=v;
			nok[v]=1;
		}
		else{
			nok[val[u]]++; //重复 则记录
		}
	}
	void print(int j){
		if(j){
			//printf("%d: %d\n",j,val[j]);
			cnt[val[j]]=1*nok[val[j]]; //这个因需求而改
			//num++;
			print(last[j]);
		}
	}
	
    void find(char *T){	
		int j=0;
		int n=strlen(T);
		for(int i=0;i<n;i++){
			int c=idx(T[i]);
			j=ch[j][c];
			if(val[j])
				print(j); 
			else if(last[j])
				print(last[j]);
		}
		
	}
	void getfail(){
		queue<int> q;
		f[0]=0;
		for(int c=0;c<sigma_size;c++){
			int u=ch[0][c];
			if(u){
				f[u]=0;
				q.push(u);
				last[u]=0;
			}
		}
		while(!q.empty()){
			int r=q.front();
			q.pop();
			for(int c=0;c<sigma_size;c++){
				int u=ch[r][c];
				if(!u){
					ch[r][c]=ch[f[r]][c];
					continue;
				}
				q.push(u);
				int v=f[r];
				while(v && !ch[v][c])
					v=f[v];
				f[u]=ch[v][c];
				last[u]=val[f[u]]? f[u]:last[f[u]];
			}
		}
	}


//不要用结构体 因为会栈溢出
int main(){
	
	int noc;
	cin>>noc;
	char temp[55];
	char text[1000000 + 10];
	while(noc--){
		init();
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>temp;
			insert(temp,i);
		}
		getfail();
		cin>>text;
		find(text);
		int ans=0;
		for(int i=1;i<=n;i++){
			ans+=cnt[i];
		}
		cout<<ans<<endl;
	}
	
	return 0;
}



























杂项
priority_queue说明
<为最大优先
>为最小优先
  priority_queue<int, vector<int>, greater<int> > q; 最小堆
 priority_queue<int > q;  最大堆
 
要有一个 head[nMax];记录 head[i]记录 i点为起点的一个临边的终点
然后有一个 edge[eMax]   i的临边的终点有  head[i]..edge[head[i]].next....edge[edge[head[i]].next].next.....0(0点不算)


素数塞法
int m=sqrt(n+0.5);
int c=0;
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++){
   if(!vis[i]){
       prime[c++]=i;
       for(int j=i*i,j<=n;j+=i)
           vis[j]=1;
   }
}

小技巧
(a+b)/2 改为 a+(b-a)/2











网络流
Dinic
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define inf 1<<26
#define maxn 1000
int s,t;//节点数，边数，源点，汇点
struct edge{
	int from,to,cap,flow;
	void make(int from,int to,int cap,int flow){
		this->from=from;
		this->to=to;
		this->cap=cap;
		this->flow=flow;
	}
};
vector<edge> edges;//边集
vector<int> G[maxn];//邻接表
bool vis[maxn];//bfs使用
int d[maxn];//起点到i的距离
int cur[maxn];//当前弧下标
void addedge(int from,int to,int cap){
	edge temp1,temp2;
	temp1.make(from,to,cap,0);
	temp2.make(to,from,0,0);
	edges.push_back(temp1);
	edges.push_back(temp2);
	int m=edges.size();
	G[from].push_back(m-2);
	G[to].push_back(m-1);
}
bool bfs(){
	memset(vis,0,sizeof(vis));
	memset(d,0,sizeof(d));
	queue<int> Q;
	Q.push(s);
	d[s]=0;
	vis[s]=1;
	while(!Q.empty()){
		int x=Q.front();
		Q.pop();
		for(int i=0;i<G[x].size();i++){
			edge &e=edges[G[x][i]];
			if(!vis[e.to]&&e.cap-e.flow>0){
				vis[e.to]=1;
				d[e.to]=d[x]+1;
				Q.push(e.to);
			}
		}
	}
	return vis[t];
}

int dfs(int x,int a){
	if(x==t||a==0)
		return a;
	int flow=0,f;
	for(int &i=cur[x];i<G[x].size();i++){
		edge &e=edges[G[x][i]];
		if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
			e.flow+=f;
			edges[G[x][i]^1].flow-=f;
			flow+=f;
			a-=f;
			if(a==0)
				break;
		}
	}
	return flow;
}
int maxflow(int ss,int tt){
	s=ss;
	t=tt;
	int flow=0;
	while(bfs()){		
		memset(cur,0,sizeof(cur));
		flow+=dfs(s,inf);		
	}
	return flow;
}
//每次case 都要初始化G 和 edges

int main(){	
	int n,np,nc,m,a,b,c,ss,tt;
	char temp;
	bool iffirst=true;
	while(cin>>n>>np>>nc>>m){
		edges.clear();
		for(int i=0;i<=n+20;i++){
			G[i].clear();
		}
		ss=n;
		tt=n=n+1;
		for(int i=1;i<=m;i++){
			cin>>temp>>a>>temp>>b>>temp>>c;
			addedge(a,b,c);
		}
		for(int i=1;i<=np;i++){
			cin>>temp>>b>>temp>>c;
			addedge(ss,b,c);
		}
		for(int i=1;i<=nc;i++){
			cin>>temp>>a>>temp>>c;
			addedge(a,tt,c);
		}
		
		cout<<maxflow(ss,tt)<<endl;
	}

	
	return 0;
}

HLPP
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define maxn 600
#define max  1200
using namespace std;
 int count1[maxn*2];
typedef struct node
{
     int num;
     int a[maxn];
}node;
 
int n,s,t,maxflow;
int map[maxn][maxn];        //边容量矩阵
int edge[maxn][maxn];       //邻接矩阵
int cur[maxn],d[maxn],e[maxn];
struct node list[2*maxn-1];
int flag;
 
void pagheuristic();
void insert(int level,int x)//加入标号为level的节点x
{    int num;
     list[level].num++;
     num = list[level].num;
     list[level].a[num] = x;
}
void BFS()//精确计算距离标号dijkstra 建层次表
{
     int p,q;int x[maxn];int i;
     fill(d,d+maxn,max);
     x[1] = t; d[t] = 0; q = 1; p = 0;
     while(p<q)
     {
         p++;
         for(i = 1; i <= edge[x[p]][0]; i++)
              if(d[ edge[x[p]][i] ] == max){
                   q++;
                   x[q] = edge[x[p]][i];
                   d[x[q]] = d[x[p]] + 1;
                   if(x[q] != s) insert(d[x[q]],x[q]);
              }
     }
     d[s] = n;
}
void push(int a,int b)
{
     int x;
     if(map[a][b] > e[a]) x = e[a];
     else x = map[a][b];
     map[a][b] -= x;
     map[b][a] += x;
     e[a] -= x;
     e[b] += x;
}
void relabel(int a)
{
     int i,min = max;
     for(i = 1; i <= edge[a][0]; i++)
         if(map[a][edge[a][i]] > 0 && d[edge[a][i]] < min)
              min = d[edge[a][i]];
     d[a] = min + 1;
     if(flag++ % n == 0) pagheuristic(); //此处加优化
}
bool check(int a)//discharge
{    bool chk = false;
     while(e[a] > 0)
     {
         if(cur[a] > edge[a][0]){
              relabel(a); chk = true; cur[a] = 1;
         }
         else if(map[a][ edge[a][cur[a]] ] > 0 && d[a] == d[ edge[a][cur[a]] ] + 1)
              push(a,edge[a][cur[a]]);//j = edge[a][cur[a]] -> b是a第j 个邻接点
         else cur[a]++;
     }
     return chk;
}
void update(int level)//将所有标号在level上的点抛上九天,会不会就是pagheuristic
{
     int j,k;
     for(j = level+1; j <= n; j++){
         for(k = 1; k <= list[j].num; k++){
              list[n+1].a[list[n+1].num + k] = list[j].a[k];
              d[list[j].a[k]] = n+1;
         }
         list[n+1].num += list[j].num;
         list[j].num = 0;
     }
}
void HLPP()
{   
     int i,b,level;
     fill(e,e+maxn,0);
     for(i = 1; i <= edge[s][0]; i++){//将所有s出发的弧充满
         b = edge[s][i];
         e[b] = map[s][b];
         e[s] -= map[s][b];
         map[b][s] = e[b];
         map[s][b] = 0;
     }
     level = n;flag = 0;
     while(level)
     {
         level--;
         for(i = list[level].num; i >= 1; i--){
              int a = list[level].a[i]; int num = list[level].num;
              if(check(a)){                                                //如果有被重标记
                   if(level > 0 &&  list[level].num == 1) update(level);//免除把余流送回S的操作,该层只剩下一个点将要断层才可update，因为在层次图中如果断层，则断层上的顶点有留流，它必流回S，这时不用再计算，把它上放到n+1 层上去
                   insert(d[a],a);                                                 
                   list[level].a[i] = list[level].a[num];                  //有标记过则排除该点，把后面没标记的移到前面来
                   list[level].num--;
                   level = d[a];                                           //level 回升
                   break;                                                       //从新的最高level重新开始
              }
         }
     }
}
//使用顺序
//初始化map
//input

//init();
    // BFS();
   // HLPP();
  // maxflow = e[t];
//满足map【u】【v】=c【u】【v】
//n表示 0.....n这n+1个点 
//二分图的话 需要构造图形  s=0 t=n;
int main(){	 
	
     void init();
     int noc,ti,p,q,v;
	 while(cin>>noc){
	 s=0;
	 memset(map,0,sizeof(map));
	 for(int i=1;i<=noc;i++){
		 map[s][i]=1;
	 }
	 n=t=6*12+12+noc+1;
	
	 for(int i=1;i<=noc;i++){
		 cin>>ti;
		 for(int j=1;j<=ti;j++){
			 
			 cin>>p>>q;  //p星期 1..7 //q第q节课 1..12
			 v=(p-1)*12+q+noc;
			 map[i][v]=1;
		 }
	 }
	 for(int i=noc+1;i<=6*12+12+noc;i++){
		 map[i][t]=1;
	 }
     
     init();
     BFS();
     HLPP();
     maxflow = e[t];
     cout<<maxflow<<endl;
	 }
	//system("pause");
	return 0;
}
void init()
{
     int i,j;
     memset(edge,0,sizeof edge);
     for(i = 0; i < n; i++)
         for(j = i+1; j <= n; j++)
              if(map[i][j]||map[j][i]){//建立邻接矩阵
                   edge[i][0]++;
                   edge[j][0]++;
                   edge[i][edge[i][0]] = j;
                   edge[j][edge[j][0]] = i;
              }
     fill(cur,cur+maxn,1);
     for(i = 0; i <= n+1; i++) list[i].num = 0;
}



//距离标号法与重标记与前移算法容易退化，所以加一个优化pagheuristic——若存在某一个k(k<n)，
//没有距离标号为k的点，则可以将标号为k--n的所有点移到标号为n+1，以此来提高效率。
//这个优化在relable时可以使用，为了节省时间，可以选在每k*n次检查一次。
void pagheuristic()
{
     
     int i,j;
     memset(count1,0,sizeof(count1));
     for(i = 1; i <= n; i++) count1[d[i]]++;
     j = 1;
     while(j < n && count1[j] != 0) j++;
     if(j == n) return;
     for(i = 1; i <= n; i++)
         if(i != s && d[i] > j && d[i] <= n)
              d[i] = n+1;
}



二分图的性质
最小点覆盖==最大匹配

匹配：
给定一个二分图，在G的一个子图G’中，如果G’的边集中的任意两条边都不依附于同一个顶点，则称G’的边集为G的一个匹配
最大匹配：
在所有的匹配中，边数最多的那个匹配就是二分图的最大匹配了
顶点覆盖：
在顶点集合中，选取一部分顶点，这些顶点能够把所有的边都覆盖了。这些点就是顶点覆盖集
最小顶点覆盖：
在所有的顶点覆盖集中，顶点数最小的那个叫最小顶点集合。
独立集：
在所有的顶点中选取一些顶点，这些顶点两两之间没有连线，这些点就叫独立集
最大独立集：
在左右的独立集中，顶点数最多的那个集合
路径覆盖：
在图中找一些路径，这些路径覆盖图中所有的顶点，每个顶点都只与一条路径相关联。
最小路径覆盖：
在所有的路径覆盖中，路径个数最小的就是最小路径覆盖了。
熟悉了这些概念之后，还有一个二分图最大匹配的K?nig定理，这个定理的内容是：最大匹配 = 最小顶点覆盖。此处不证明其正确性。有了这个定理之后还可以得出一些二分图特有的公式：
最小路径覆盖=最大独立集 = 顶点个数 – 最小顶点覆盖（最大匹配）



匈牙利算法
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#define maxn 500
using namespace std;
struct Pool{
	int next,v;
}p[maxn*maxn];
int head[maxn],num;
void add(int a,int b){
	p[++num].next=head[a];
	p[num].v=b;
	head[a]=num;
}
int n,m;//m为 x集的个数 y集的点为 m+1.....n
int mat[maxn];////match[y]==x 则 x 与y匹配
bool used[maxn];
bool crosspath(int x){
	int k;
	for(int tmp=head[x],k;tmp;tmp=p[tmp].next){
		k=p[tmp].v;
		if(!used[k]){
			used[k]=true;
			if(!mat[k]||crosspath(mat[k])){ 
				mat[k]=x;
				return true;
			}
		}
	}
	return false;
}
int dfs(){
	int ans=0;
	for(int i=1;i<=m;i++){
		memset(used,false,sizeof(used));
		if(crosspath(i))
			ans++;
	}
	return ans;
}
void build(int c){
	int temp,a,b;
	for(int i=1;i<=c;i++){
		cin>>temp>>a>>b;
		if(a==0||b==0)
			continue;
		add(a,m+b);
	}
}
//输入 m 和n m为 x集的个数 y集的点为 m+1.....n
//每个case 在之前要memset(head,0,sizeof(head));
      // memset(mat,0,sizeof(mat));  
//num=0;
//build();
//dfs()为结果
int main(){
	int a,b,c;
	while(cin>>a&&a){
		cin>>b>>c;
		m=a;
		n=a+b;
		num=0;
		memset(head,0,sizeof(head));
                                memset(mat,0,sizeof(mat)); 
		build(c);
		cout<<dfs()<<endl;

	}
	return 0;
}
















二分搜索
浮点
while(high-low>eps){
                        mid=(high+low)/2;
                        if(judge(mid)){
                                res=mid;
                                low=mid;
                        }
                        else{
                                res=mid;
                                high=mid;
                        }
                }
                res+=1e-6;

整数
while(low<=high){
                        mid=low+(high-low)/2;
                        if(judge(mid)){
                                low=mid+1;
                                res=mid;
                        }
                        else{
                                high=mid-1;
                        }

                }

















Oj代码
#include <cstdio>
#include <cstring>
char str[30],na[30],ch;
char nam[100][30];
int tot[100],cnt[100],d[100][20],fa[100][20],last[100][20],lst[100][20],ans[100];
int cas,n,m,i,j,tim,tmp;
void swap(int i,int j)
{
        int tmp,k; char ch;
        tmp=cnt[i]; cnt[i]=cnt[j]; cnt[j]=tmp;
        tmp=tot[i]; tot[i]=tot[j]; tot[j]=tmp;
        for (k=0;k<30;k++)
        {
                ch=nam[i][k]; nam[i][k]=nam[j][k]; nam[j][k]=ch;
        }
        for (k=0;k<20;k++)
        {
                tmp=last[i][k]; last[i][k]=last[j][k]; last[j][k]=tmp;
                tmp=lst[i][k]; lst[i][k]=lst[j][k]; lst[j][k]=tmp;
        }
}
int cmp(int i,int j,int p)
{
        int k,l1,l2;
        if (cnt[i]<cnt[j]) return 1;
        if (cnt[i]>cnt[j]) return 0;
        if (tot[i]>tot[j]) return 1;
        if (tot[i]<tot[j]) return 0;
        for (k=cnt[i];k>0;k--)
        {
                if (lst[i][k]>lst[j][k]) return 1;
                if (lst[i][k]<lst[j][k]) return 0;
                if (last[i][k]>last[j][k]) return 1;
                if (last[i][k]<last[j][k]) return 0;
        }
        if (p)
        {
                l1=strlen(nam[i]); l2=strlen(nam[j]);
                k=0;
                while (k<l1||k<l2)
                {
                        if (k>=l2) return 1;
                        if (k>=l1) return 0;
                        if (nam[i][k]>nam[j][k]) return 1;
                        if (nam[i][k]<nam[j][k]) return 0;
                        k++;
                }
        }
        return -1;
}
int main()
{
        scanf("%d",&cas);
        while (cas--)
        {
                memset(d,0,sizeof(d));
                memset(tot,0,sizeof(tot));
                memset(fa,0,sizeof(fa));
                memset(last,0,sizeof(last));
                memset(cnt,0,sizeof(cnt));
                memset(ans,0,sizeof(ans));
                memset(lst,0,sizeof(lst));
                scanf("%d%d",&n,&m);
                for (i=1;i<=n;i++) scanf("%s",nam[i]);
                for (i=1;i<=m;i++)
                {
                        scanf("%d%s %c %s",&tim,na,&ch,str);
                        tmp=ch-'A'+1;
                        for (j=1;j<=n;j++)
                        if (strcmp(na,nam[j])==0)
                        {
                                if (d[j][tmp]) break;
                                if (strcmp(str,"rejected")==0) fa[j][tmp]++;
                                else
                                {
                                        d[j][tmp]=1; cnt[j]++;
                                        tot[j]+=tim+fa[j][tmp]*20;
                                        last[j][cnt[j]]=tot[j];
                                        lst[j][cnt[j]]=tim;
                                }
                        }
                }

                for (i=1;i<n;i++)
                for (j=1;j<=n-i;j++)
                if (cmp(j,j+1,1)==1) swap(j,j+1);
                for (i=1;i<=n;i++)
                {
                        if (i>1&&cmp(i,i-1,0)==-1) ans[i]=ans[i-1]; else ans[i]=i;
                        printf("%d %s %d %d\n",ans[i],nam[i],cnt[i],tot[i]);
                }
        }
        return 0;
}