//做啦好久老是WA，不知到为什么，刚刚开始吧他们都设成是双浮点型，老是过不了；改成整形就过啦；

//后来又是超时，吧cin改成scanf();果断过！！！！！

#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
#define eps 1e-6
const int MAXN=3005;
const int INF=1<<28;
int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny;int dx[MAXN],dy[MAXN],dis;
bool vst[MAXN];
struct Node1{
    int x,y,s;
}guests[MAXN];
struct Node2{
    int x,y;
}um[MAXN];
double distance(Node1 a,Node2 b){
    double x=a.x-b.x; 
    double y=a.y-b.y;   
    return sqrt(x*x+y*y);
} 
bool searchP(void){
    queue<int> Q;
    dis = INF;
    memset(dx, -1, sizeof(dx));
    memset(dy, -1, sizeof(dy));
    for (int i = 0; i < Nx; i++)
        if (Mx[i] == -1){
            Q.push(i); dx[i] = 0;
        }
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            if (dx[u] > dis) break;
            for (int v = 0; v < Ny; v++)
                if (g[u][v] && dy[v] == -1) {
                    dy[v] = dx[u]+1;
                    if (My[v] == -1) dis = dy[v];
                    else{
                        dx[My[v]] = dy[v]+1;
                        Q.push(My[v]);
                    }
                }
        }
        return dis != INF;
}
bool DFS(int u){
    for (int v = 0; v < Ny; v++)
        if (!vst[v] && g[u][v] && dy[v] == dx[u]+1) {
            vst[v] = 1;
            if (My[v] != -1 && dy[v] == dis) continue;
            if (My[v] == -1 || DFS(My[v])) {
                My[v] = u; Mx[u] = v;
                return 1;
            }
        }
        return 0;
}
int MaxMatch(void){
    int res = 0;
    memset(Mx, -1, sizeof(Mx));
    memset(My, -1, sizeof(My));
    while (searchP()) {
        memset(vst, 0, sizeof(vst));
        for (int i = 0; i < Nx; i++)
            if (Mx[i] == -1 && DFS(i)) res++;
    }
    return res;
}
int main(){
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);   
    int n,m,t,i,j;   
    int T,iCase=0;  
    scanf("%d",&T); 
    while(T--)   
    {     
        iCase++;    
        scanf("%d",&t); 
        scanf("%d",&m);   
        for(i=0;i<m;i++)      
            scanf("%d%d%d",&guests[i].x,&guests[i].y,&guests[i].s);   
        scanf("%d",&n);     
        for(i=0;i<n;i++)    
            scanf("%d%d",&um[i].x,&um[i].y);
        Nx=m;Ny=n;      
        memset(g,0,sizeof(g));    
        for(i=0;i<m;i++)    
        {           
            for(j=0;j<n;j++) 
            {             
                if(distance(guests[i],um[j])/guests[i].s-t<eps)    
                {                
                    g[i][j]=1;       
                }       
            }       
        }           
        printf("Scenario #%d:\n%d\n\n",iCase,MaxMatch());  
    }   
    return 0;
}      

#include <iostream>
#include <cstdio>
using namespace std;
int const MAXN = 250;
int graph[MAXN][MAXN], cnt[MAXN];
//邻接表矩阵，点度
bool ck[MAXN];//记录是否被访问
int match[MAXN];//匹配数组，记录右端到左端的匹配
int V, E;//点数、边数
bool search(int G[][MAXN], int k)
{//找增广边
    for(int i = 0; i < cnt[k]; i++)
    {
        int p = G[k][i];
        if(ck[p])
        {
            ck[p] = false;
            int t = match[p];
            if(t == -1 || search(G, t) )
            {
                match[p] = k;
                return true;
            }
            //match[p] = t;
        }
    }
    return false;
}

int hungary(int G[][MAXN], int left)
{//传入矩阵和左端点数，传出匹配的对数
    int answer(0);
    int i, j;
    for(i = 0; i < V; i++)        // V为右端顶点数
    {
        match[i] = -1;
    }
    for(i = 0; i < left; i++)
    {
       for(j = 0; j < V; j++)
       {
            ck[j] = true;
        }
       if(search(G, i))
       {
            ++answer;
       }
    }
    return answer;
}

 

/**********************************************
二分图匹配（Hopcroft-Carp的算法）。
初始化：g[][]邻接矩阵
调用：res=MaxMatch();  Nx,Ny要初始化！！！
时间复杂大为 O(V^0.5 E)

适用于数据较大的二分匹配 
***********************************************/ 
const int MAXN=3001;
const int INF=1<<28;
int g[MAXN][MAXN],Mx[MAXN],My[MAXN],Nx,Ny;
int dx[MAXN],dy[MAXN],dis;
bool vst[MAXN];
bool searchP()
{
    queue<int>Q;
    dis=INF;
    memset(dx,-1,sizeof(dx));
    memset(dy,-1,sizeof(dy));
    for(int i=0;i<Nx;i++)
        if(Mx[i]==-1)
        {
            Q.push(i);
            dx[i]=0;
        }  
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        if(dx[u]>dis)  break;
        for(int v=0;v<Ny;v++)
            if(g[u][v]&&dy[v]==-1)
            {
                dy[v]=dx[u]+1;
                if(My[v]==-1)  dis=dy[v];
                else
                {
                    dx[My[v]]=dy[v]+1;
                    Q.push(My[v]);
                }    
            }    
    }  
    return dis!=INF;    
}    
bool DFS(int u)
{
    for(int v=0;v<Ny;v++)
       if(!vst[v]&&g[u][v]&&dy[v]==dx[u]+1)
       {
           vst[v]=1;
           if(My[v]!=-1&&dy[v]==dis) continue;
           if(My[v]==-1||DFS(My[v]))
           {
               My[v]=u;
               Mx[u]=v;
               return 1;
           }    
       }  
    return 0;  
}
int MaxMatch()
{
    int res=0;
    memset(Mx,-1,sizeof(Mx));
    memset(My,-1,sizeof(My));
    while(searchP())
    {
        memset(vst,0,sizeof(vst));
        for(int i=0;i<Nx;i++)
          if(Mx[i]==-1&&DFS(i))  res++;
    }
    return res;   
}    
    

字符串匹配算法:KMP学习心得

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。

#include<iostream>
using namespace std;
int a[1000010],b[10010],next[10010];
int lena,lenb;

void inset()
{
    int i;
    scanf("%d%d",&lena,&lenb);
    for(i=0;i<lena;i++)
        scanf("%d",&a[i]);
    for(i=0;i<lenb;i++)
        scanf("%d",&b[i]);
}




void Gurm()
{
    int j=0,k=-1;
    next[0]=-1;
    while(j<lenb)
    {
        if(k==-1 || b[j]==b[k])
        {
            ++j;
            ++k;
            next[j]=k;
        }
        else
        {
            k=next[k];
        }
    }
}



int kmp()
{
    int i=0,j=0;
    Gurm();
    while(i<lena && j<lenb)
    {
        if(j==-1 || a[i]==b[j] )
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    if(j<lenb)  return -1;
    else return i-j+1;
}





int main()
{
    //freopen("D:\\in.txt","r",stdin);
    int R;scanf("%d",&R);
    while(R--)
    {
        inset();
        printf("%d\n",kmp());
    }
    return 0;
}
 

KMP:next[]的应用。

 * 一般next[i]与优化next[i]的区别：

 *如果模式串p下标为i的字符（字符第一个的下标为0）的前k个字符与开头前k个字符相等（0=<k<i 注意这里没有等于i）

 *     对于一般的next[i]，不管p[i]是否等于p[k+1]，next[i]都是等于k;
 *     对于优化后的next[i]，如果p[i]不等于p[k+1],则next[i]=k,反之,next[i]=0.

 * 这题的next[]是从0求到n,有n+1个值，因此对于next[i]=k的意义（0除外）就为：字符串下标为i的前k-1个字符与字符串头k个字符相等(上面提到的next[i]是与前k个字符与头k个字符相等next[i]才等于k)。
 * 对于长度为i个字符串，i-next[i]（满足i % （i-next[i]）==0)代表的意义就是 长度为i的字符串 的 最小循环子串的长度
 *  因此 字符串中存在周期的子串的最大循环次数=i/ (i-next[i]);
 *
 

#include<stdio.h>
#include<string.h>
 
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
 
bool init()
{
        int _x,_y;
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        ans=0;
        if(scanf("%d%d",&n,&m)==EOF)return false;
        for(int i=1;i<=n;i++)
        {
                scanf("%d",&_x);
                for(int j=0;j<_x;j++)
                {
                        scanf("%d",&_y);
                        g[ i ][_y]=true;
                }
        }
        return true;
}
 
bool find(int a)
{
        for(int i=1;i<=m;i++)
        {
                if(g[a][ i ]==1&&!b[ i ])
                {
                        b[ i ]=true;
                        if(link[ i ]==0||find(link[ i ]))
                        {
                                link[ i ]=a;
                                return true;
                        }
                }
        }
        return false;
}
 
int main()
{
        while(init())
        {
                for(int i=1;i<=n;i++)
                {
                        memset(b,0,sizeof(b));
                        if(find(i))ans++;
                }
                printf("%d\n",ans);
        }
}

每次增广时间为O(E),最多进行O(V)次迭代,时间复杂度为O(VE).