hdoj1068 最大独立集
小试一下写的模板

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 10010
#define maxe 2000010
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
int color[maxn];
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        if(color[i]==2) continue;
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
void dfs2(int cur,int c)
{
    color[cur]=c;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(color[v]==3-c) continue;
        dfs2(v,3-c);
    }
    return;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n))
    {
        int num;
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d: (%d)",&u,&num);u++;
            for(j=1;j<=num;j++)
            {
                scanf("%d",&v);v++;
                add(u,v);add(v,u);
            }
        }
        memset(color,0,sizeof(color));
        for(i=1;i<=n;i++)
            if(!color[i]) dfs2(i,1);
        int ans=xyl();
        printf("%d\n",n-ans);


    }

    return 0;
}

hdoj1150
题意：两个机器，第一个机器有n1种模式，第二个机器有n2种模式，给出m个任务，每个任务可以用机器一的某一模式或机器二的某一模式完成，切换模式需要重启机器，两个机器初始都是模式0，问完成这些任务最少需要重启几次。
思路：建立二分图：X部n1个点，Y部n2个点，一个任务可以在机器一的模式u或机器二的模式v下完成，则连边(u,n1+v)。这样，图中的每条边相当于一个任务，现在要求完成所有任务所需的最少重启次数，本质就是选出最少的点来覆盖所有的边，即二分图的最小点覆盖。
注意：由于初始是0模式，所以端点为0的边是不用连的，因为不用重启就可以完成这些任务。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 300+10
#define maxe 10000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n1,n2,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n1;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n1) && n1!=0)
    {
        scanf("%d%d",&n2,&m);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&j,&u,&v);
            if(!u || !v) continue;
            u++;v++;
            add(u,n1+v);add(n1+v,u);
        }
        int ans=xyl();
        printf("%d\n",ans);
    }
    return 0;
}

hdoj1151
DAG的最小路径覆盖

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 300+10
#define maxe 40000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m,cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j,t;
    int u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;memset(head,-1,sizeof(head));
        while(m--)
        {
            scanf("%d%d",&u,&v);
            add(u,n+v);
        }
        printf("%d\n",n-xyl());



    }

    return 0;
}

hdoj1179 Ollivanders: Makers of Fine Wands since 382 BC.
裸题

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 200+10
#define maxe 10000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&m,&n))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            int k;
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d",&j);
                add(i,n+j);
            }
        }
        printf("%d\n",xyl());
    }
    return 0;
}

hdoj1281
在某篇网络流的论文中出现过类似的题，行列见图,以行为x部，列为y部。如果可以在(i,j)放车，那么连弧,求最大匹配。
关键边一定是最大匹配中的某些边，因此枚举删去最大匹配的边，求最大匹配即可。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 300+10
#define maxe 
typedef struct Edge{
    bool flag;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n1,n2,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
int match2[maxn];
inline void add(int u,int v)
{
    edge[cnt].flag=1;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v] || !edge[i].flag) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n1;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v;
    int key,cases=0;
    while(scanf("%d%d%d",&n1,&n2,&m)!=EOF)
    {
        key=0;cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,n1+v);
        }
        int ans=xyl();
        for(i=n1+1;i<=n1+n2;i++)
            match2[i]=match[i];
        for(i=n1+1;i<=n1+n2;i++)
        {
            u=match2[i];
            if(!u) continue;
            for(j=head[u];j!=-1;j=edge[j].next)
            {
                if(edge[j].to!=i) continue;
                edge[j].flag=0;
                v=j;
                break;
            }
            int tmp=xyl();
            if(ans!=tmp) key++;
            edge[v].flag=1;
        }
        printf("Board %d have %d important blanks for %d chessmen.\n",++cases,key,ans);
    }
    return 0;
}

hdoj1498 50 years, 50 colors
题意：给出n*n矩阵，map[i][j](1<=map[i][j]<=50)表示气球的颜色值。k表示可以操作k次，每次操作可以删除一行或一列的某同一颜色的气球。问哪种颜色的气球是无法通过k次操作删除完的。将结果升序排列，否则输出-1。
注意点：如果认为，对于某一颜色，如果该颜色分布在i行，j列，只要i>k && j>k就无法删除完就大错特错了，即使i>k && j>k仍然有可能通过选定某些行和某些列来消除完这种颜色的气球（画画图就能明白了）
思路：行列建图，对于颜色w，如果map[i][j]=w那么建弧，这样每条边就表示需要删除的点，那么对于点i(i<=n)，选中i就表示删除了第i行上的颜色为w的气球，即覆盖了和i关联的边。那么问题的实质就是求最小点覆盖=ans，如果ans>k那么说明这种颜色的点不能通过k次操作消除完。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 300+10
#define maxe 20000+10
typedef struct Edge{
    bool flag;
    int w;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,k;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v,int w)
{
    edge[cnt].flag=1;edge[cnt].w=w;edge[cnt].from=u;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v] || !edge[i].flag) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int ans[55],anscnt;
int main()
{
    int i,j;
    int u,v,tmp;
    while(~scanf("%d%d",&n,&k) && !(n==0 && k==0))
    {
        anscnt=cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%d",&tmp);
                add(i,n+j,tmp);
            }
        for(i=1;i<=50;i++)
        {
            bool in=0;
            for(j=0;j<=cnt-1;j++)
                if(edge[j].w!=i) edge[j].flag=0;
                else in=1;
            if(!in) {for(j=0;j<=cnt-1;j++) edge[j].flag=1;continue;}
            if(xyl()>k) ans[++anscnt]=i;
            for(j=0;j<=cnt-1;j++) edge[j].flag=1;
        }
        if(anscnt==0) {printf("-1\n");continue;}
        printf("%d",ans[1]);
        for(i=2;i<=anscnt;i++) printf(" %d",ans[i]);
        printf("\n");
    }
    return 0;
}

hdoj1507 Uncle Tom’s Inherited Land*
最大匹配，输出方案

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 20000+10
#define maxe 300+10
typedef struct Edge{
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].from=u;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool map[110][110];
inline bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m && map[x][y]) return 1;
    return 0;
}
inline int index(int x,int y)
{
    return (x-1)*m+y;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i,j;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            if((i+j)&1) continue;
            int tmp=index(i,j);
            memset(use,0,sizeof(use));
            if(dfs(tmp)) ans++;
        }
    return ans;
}
int main()
{
    int i,j;
    int u,v,k;
    while(~scanf("%d%d",&n,&m) && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(map,1,sizeof(map));
        scanf("%d",&k);
        while(k--)
        {
            scanf("%d%d",&u,&v);
            map[u][v]=0;
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(!map[i][j] || (i+j)&1) continue;
                if(judge(i-1,j)) add(index(i,j),index(i-1,j));
                if(judge(i+1,j)) add(index(i,j),index(i+1,j));
                if(judge(i,j-1)) add(index(i,j),index(i,j-1));
                if(judge(i,j+1)) add(index(i,j),index(i,j+1));
            }
        printf("%d\n",xyl());
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if(!((i+j)&1) || !match[index(i,j)]) continue;
                int tmp=match[index(i,j)];
                int tmpx=tmp%m==0?tmp/m:tmp/m+1;
                int tmpy=tmp-tmp/m*m;
                if(!tmpy) tmpy=m;
                printf("(%d,%d)--(%d,%d)\n",tmpx,tmpy,i,j);
            }
        printf("\n");
    }
    return 0;
}

hdoj1528 Card Game Cheater
思路：对于第二个人的牌i和第一个人的牌j，如果牌i大于牌j，则连弧，做最大匹配即可

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 100+10
#define maxe 1000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int num[300];
char map1[30][2],map2[30][2];
bool greater(char a[],char b[])
{
    if(a[0]!=b[0]) return num[a[0]]>num[b[0]];
    return num[a[1]]>num[b[1]];
}
int main()
{
    int i,j;
    int u,v;
    int t;
    for(i='2';i<='9';i++)
        num[i]=i-'0'-1;
    num['T']=9;num['J']=10;num['Q']=11;num['K']=12;num['A']=13;
    num['C']=1;num['D']=2;num['S']=3;num['H']=4;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;memset(head,-1,sizeof(head));
        scanf("%d",&n);getchar();
        for(i=1;i<=n;i++)
        {
            scanf("%c%c",&map1[i][0],&map1[i][1]);
            getchar();
        }
        for(i=1;i<=n;i++)
        {
            scanf("%c%c",&map2[i][0],&map2[i][1]);
            getchar();
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(!greater(map2[i],map1[j])) continue;
                add(i,n+j);
            }
        printf("%d\n",xyl());
    }
    return 0;
}

hdoj2063 过山车
裸题

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 1000+10
#define maxe 1000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v,k;
    while(~scanf("%d",&k) && k)
    {
        scanf("%d%d",&n,&m);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=k;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,n+v);
        }
        printf("%d\n",xyl());
    }
    return 0;
}

hdoj2119 Matrix
最小点覆盖，与上面某题类似

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 200+10
#define maxe 10000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    int tmp;
    while(~scanf("%d",&n) && n)
    {
        scanf("%d",&m);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&tmp);
                if(!tmp) continue;
                add(i,n+j);
            }
        printf("%d\n",xyl());
    }
    return 0;
}

hdoj2444 The Accomodation of Students
先交叉染色判断是否是二分图，在做最大匹配

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 200+10
#define maxe 40000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int color[maxn];
bool dfs2(int cur,int c)
{
    if(color[cur]==c) return 1;
    if(color[cur]==3-c) return 0;
    color[cur]=c;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(!dfs2(v,3-c)) return 0;
    }
    return 1;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        memset(color,0,sizeof(color));
        if(!dfs2(1,1)) {printf("No\n");continue;}
        printf("%d\n",xyl()/2);
    }
    return 0;
}

hdoj1045 Fire Net
思路：经典的行列建图变形，由于有了墙壁，所以不是每行每列只能有一个，其实质是需要自己计算一个格子所处的“行”和“列”。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 100+10
#define maxe 10000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
char map[5][5];
int row[5][5],col[5][5];
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n) && n)
    {
        getchar();
        cnt=0;memset(head,-1,sizeof(head));
        char tmpr[30],tmpc[30];
        int rx[30],ry[30];
        int cx[30],cy[30];
        int count1=0,count2=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%c",&map[i][j]);
                tmpr[++count1]=map[i][j];
                rx[count1]=i;ry[count1]=j;
            }
            tmpr[++count1]='X';
            getchar();
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                tmpc[++count2]=map[j][i];
                cx[count2]=j;cy[count2]=i;
            }
            tmpc[++count2]='X';
        }
        int cur;
        cur=0;i=1;
        while(tmpr[i]=='X' && i<=count1) i++;
        while(i<=count1)
        {
            cur++;
            while(i<=count1 && tmpr[i]=='.')
            {
                row[rx[i]][ry[i]]=cur;i++;
            }
            while(i<=count1 && tmpr[i]=='X') i++;
        }
        int nn=cur;
        i=1;
        while(tmpc[i]=='X' && i<=count2) i++;
        while(i<=count2)
        {
            cur++;
            while(i<=count2 && tmpc[i]=='.')
            {
                col[cx[i]][cy[i]]=cur;i++;
            }
            while(i<=count2 && tmpc[i]=='X') i++;
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(map[i][j]=='X') continue;
                add(row[i][j],col[i][j]);
            }
        n=nn;
        printf("%d\n",xyl());
    }
    return 0;
}

hdoj1350 Taxi Cab Scheme
如果某个cab在完成任务i后还可以完成j，那么在i任务的结束点向j任务的开始点连边

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define maxn 4000+10
#define maxe 1000000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
typedef struct Point{
    int x,y;
}Point;
Point bp[510],ep[510];
int bt[510],et[510];
int dist(Point a,Point b)
{
    return abs(a.x-b.x)+abs(a.y-b.y);
}
int main()
{
    int i,j,t;
    int u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int h,m;
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d:%d %d%d%d%d",&h,&m,&bp[i].x,&bp[i].y,&ep[i].x,&ep[i].y);
            bt[i]=h*60+m;et[i]=bt[i]+dist(bp[i],ep[i]);
            add(i,3*n+i);
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j) continue;
                if(et[i]+dist(ep[i],bp[j])+1<=bt[j]) add(n+i,2*n+j);
                if(et[j]+dist(ep[j],bp[i])+1<=bt[i]) add(n+j,2*n+i);
            }
        n*=2;
        printf("%d\n",n-xyl());
    }
    return 0;
}

hdoj3118 Arbiter
题意：最少去掉几条边可以使图不含奇圈。
思路：一个图是二分图的充要条件是它不含奇圈，且含有至少两个点。由于n很小，所以可以二进制枚举二分图的X部和Y部，然后判断要去掉几条边。

#include<stdio.h>
#include<string.h>
#define maxn 20
#define maxe 90000+10
typedef struct Edge{
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt;
int n,m;
int ans;
void add(int u,int v)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
int main()
{
    int t;
    int i,j;
    int u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        ans=100000000;cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        for(i=0;i<=(1<<n)-1;i++)
        {
            int tmp=0;
            for(j=0;j<=cnt-1;j++)
            {
                u=edge[j].from;v=edge[j].to;
                if(((i&(1<<u)) && (i&(1<<v))) || (!(i&(1<<u)) && !(i&(1<<v))))
                    tmp++;
            }
            if(tmp<ans) ans=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}

hdoj3729 I’m Telling the Truth
思路：求字典序最大的二分匹配方案，做匈牙利算法的时候倒着枚举二分图一边的点即可

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100100+10
#define maxe 10000000+10
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=n;i>=1;i--)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j,t;
    int u,v;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&u,&v);
            for(j=u;j<=v;j++)
                add(i,n+j);
        }
        int num=xyl();
        printf("%d\n",num);
        int ans[100],count=0;
        for(i=n+1;i<=n+100000;i++)
            if(match[i])
            {
                ans[++count]=match[i];
            }
        sort(ans+1,ans+1+count);
        bool flag=1;
        for(i=1;i<=num;i++)
        {
            if(flag){printf("%d",ans[i]);flag=0;}
            else printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

hdoj2389 Rain on your Parade
匈牙利果断TLE

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#include<math.h>
#define maxn 6000+10
#define maxe 9000000+10
#define eps 1e-8
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
typedef struct Point{
    int x,y;
}Point;
Point p[maxn],b[maxn];
int sp[maxn];
double dist(Point a,Point b)
{
    return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
int main()
{
    int i,j,t;
    int u,v,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        int time;
        double dis;
        cnt=0;memset(head,-1,sizeof(head));
        scanf("%d%d",&time,&n);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&p[i].x,&p[i].y,&sp[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
            scanf("%d%d",&b[i].x,&b[i].y);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                dis=dist(p[i],b[j]);
                if(dis<(double)(time*sp[i])+eps)
                    add(i,n+j);
            }
        }
        printf("Scenario #%d:\n%d\n\n",++cases,xyl());
    }
    return 0;
}

hk无压力

/**
    hk算法O(sqrt(V)*E)
    每次bfs找到的增广路集合中的增广路都是一样长的，且随着bfs，长度是递增的
**/
#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#define maxn 3000+10
#define maxe 10000000+10
#define eps 1e-8
using namespace std;
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn],cnt;
int n,m;
int mx[maxn],my[maxn],dx[maxn],dy[maxn];
bool use[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool bfs()
{
    int i;
    bool res=0;
    queue<int> q;
    for(i=1;i<=n;i++)
        if(!mx[i]) q.push(i);
    memset(dx,0,sizeof(dx));
    memset(dy,0,sizeof(dy));
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(i=head[u];i!=-1;i=edge[i].next)
        {
            int v=edge[i].to;
            if(!dy[v])
            {
                dy[v]=dx[u]+1;
                if(!my[v]) res=1;
                else
                {
                    dx[my[v]]=dy[v]+1;
                    q.push(my[v]);
                }
            }
        }
    }
    return res;
}
bool dfs(int u)
{
    int i,j;
    for(i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dy[v]==dx[u]+1)
        {
            dy[v]=0;
            if(!my[v] || dfs(my[v]))
            {
                mx[u]=v;my[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int hk()
{
    int ans=0;
    memset(mx,0,sizeof(mx));
    memset(my,0,sizeof(my));
    while(bfs())
    {
        for(int i=1;i<=n;i++)
            if(!mx[i] && dfs(i)) ans++;
    }
    return ans;
}
typedef struct Point{
    int x,y;
}Point;
Point p[maxn],b[maxn];
int sp[maxn];
double dist(Point a,Point b)
{
    return sqrt((double)((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
}
int main()
{
    int i,j,t;
    int u,v,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        int time;
        double dis;
        cnt=0;memset(head,-1,sizeof(head));
        scanf("%d%d",&time,&n);
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&p[i].x,&p[i].y,&sp[i]);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
            scanf("%d%d",&b[i].x,&b[i].y);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                dis=dist(p[i],b[j]);
                if(dis<(double)(time*sp[i])+eps)
                    add(i,j);
            }
        }
        printf("Scenario #%d:\n%d\n\n",++cases,hk());
    }
    return 0;
}

hdoj1054 Strategic Game
思路：树的最小边覆盖，可以贪心或者dp或者当成二分图来做，因为无向树一定是二分图。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 1500+10
#define maxe 3000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    int u,v;
    while(~scanf("%d",&n))
    {
        cnt=0;memset(head,-1,sizeof(head));
        int num;
        for(i=1;i<=n;i++)
        {
            scanf("%d:(%d)",&u,&num);u++;
            for(j=1;j<=num;j++)
            {
                scanf("%d",&v);v++;
                add(u,v);add(v,u);
            }
        }
        printf("%d\n",xyl()/2);


    }
    return 0;
}

hdoj3605 Escape
哈哈，第一道二分图多重匹配，以前用最大流a过，用最大流必须缩点，将具有相同选择状态的人合并
用匈牙利复杂度比最大流低，开始use数组开成了十万，结果memset一下下就超时了，慎用memset，，其实开成10+5就行了。

#include<stdio.h>
#include<string.h>
#define maxn 100010+10
#define maxe 2000000+10
#define maxl 100000+10
#define maxr 10+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxr];
int maxy[maxr],num[maxr],match[maxr][maxl];
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i,j;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(num[v]<maxy[v])
        {
            num[v]++;
            match[v][num[v]]=cur;
            return 1;
        }
        else
        {
            for(j=1;j<=num[v];j++)
            {
                if(dfs(match[v][j]))
                {
                    match[v][j]=cur;
                    return 1;
                }
            }
        }
    }
    return 0;
}
bool xyl()
{
    int i;
    memset(num,0,sizeof(num));
    for(i=m+1;i<=m+n;i++)
    {
        memset(use,0,sizeof(use));
        if(!dfs(i)) return 0;//左侧i点出发找不到增广轨，那么以后也不会找到，即这个人无法匹配
    }
    return 1;
}
void scan(int &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');    }    num=in-'0';
        while(in=getchar(),in>='0'&&in<='9')        num*=10,num+=in-'0';
        if(neg)        num=0-num;
}
int main()
{
    int i,j;
    int u,v,tmp;
    while(~scanf("%d%d",&n,&m))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scan(tmp);
                if(tmp) add(m+i,j);
            }
        }
        for(i=1;i<=m;i++) scan(maxy[i]);
        printf("%s\n",xyl()?"YES":"NO");
    }
    return 0;
}

hdoj1669 Jamie’s Contact Groups
二分答案，做多重匹配

#include<stdio.h>
#include<string.h>
#define maxn 1500+10
#define maxe 750000+10
#define maxl 1000+10
#define maxr 500+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxr];
int maxy[maxr],num[maxr],match[maxr][maxl];
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i,j;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(num[v]<maxy[v])
        {
            num[v]++;
            match[v][num[v]]=cur;
            return 1;
        }
        else
        {
            for(j=1;j<=num[v];j++)
            {
                if(dfs(match[v][j]))
                {
                    match[v][j]=cur;
                    return 1;
                }
            }
        }
    }
    return 0;
}
bool xyl()
{
    int ans=0,i;
    memset(num,0,sizeof(num));
    for(i=m+1;i<=m+n;i++)
    {
        memset(use,0,sizeof(use));
        if(!dfs(i)) return 0;
    }
    return 1;
}
int bsearch(int l,int r)
{
    int mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        for(int i=1;i<=m;i++) maxy[i]=mid;
        if(xyl()) r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
    int i,j;
    int u,v;
    char s[20];
    while(scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            scanf("%s",s);
            char c;
            int tmp=0;
            c=getchar();
            c=getchar();
            while(c!='\n')
            {
                if(c==' ')
                {
                    add(m+i,tmp+1);
                    tmp=0;
                }
                else
                {
                    tmp=tmp*10+c-'0';
                }
                c=getchar();
            }
            add(m+i,tmp+1);
        }
        printf("%d\n",bsearch(1,1000));

    }
    return 0;
}

hdoj2236
思路：二分差值，在每次二分的时候枚举下界。如果是枚举下界，对于每个下界二分差值，结果无情的TLE了。。。
技巧：如果题目要求是左侧都要匹配，那么匈牙利算法改成if(!dfs(i)) return 0可以节省时间，因为一个点现在找不到增广轨，以后也肯定找不到。

/**
匈牙利算法O(nm)
**/
#include<stdio.h>
#include<string.h>
#define maxn 200+10
#define maxe 10000+10
typedef struct Edge{
    bool flag;
    int w;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].flag=1;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        if(!edge[i].flag) continue;
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
bool xyl()
{
    int i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(!dfs(i)) return 0;
    }
    return 1;
}
int ans,maxd,mind;
int bsearch(int l,int r)
{
    int i,j;
    int m;
    while(l<=r)
    {
        m=(l+r)/2;
        bool flag=0;
        for(i=1;i<=maxd-m;i++)
        {
            for(j=0;j<=cnt-1;j++)
                if(edge[j].w>=i && edge[j].w<=i+m) edge[j].flag=1;
                else edge[j].flag=0;
            if(xyl()) {flag=1;break;}
        }
        if(!flag) l=m+1;
        else r=m-1;
    }
    return l;
}
int main()
{
    int i,j;
    int t,tmp;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        cnt=0;memset(head,-1,sizeof(head));
        ans=0x3f3f3f3f,maxd=-1,mind=0x3f3f3f3f;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%d",&tmp);
                add(i,n+j,tmp);
                if(tmp>maxd) maxd=tmp;
                if(tmp<mind) mind=tmp;
            }
        int maxcha=maxd-mind;
        printf("%d\n",bsearch(0,maxcha));


    }
    return 0;
}

hdoj1083 Courses
裸的最大匹配

#include<stdio.h>
#include<string.h>
#define maxn 400+10
#define maxe 120000+10
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m;
int cnt;
bool use[maxn];
int match[maxn];//match[i]表示i点匹配的点，i为右侧的点
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
bool xyl()
{
    int ans=0,i;
    memset(match,0,sizeof(match));
    for(i=1;i<=n;i++)
    {
        memset(use,0,sizeof(use));
        if(!dfs(i)) return 0;
    }
    return 1;
}
int main()
{
    int i,j;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            int cc,tmp;
            scanf("%d",&cc);
            for(j=1;j<=cc;j++)
            {
                scanf("%d",&tmp);
                add(i,n+tmp);
            }
        }
        if(xyl()) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

hdoj2458 Kindergarten
裸的二分图最大团

#include<stdio.h>
#include<string.h>
#define maxn 410
#define maxe 40010
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n1,n2,m,cnt;
int match[maxn];
bool use[maxn];
void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n1;i++)
    {
        memset(use,0,sizeof(use));
        if(match[i]) continue;
        if(dfs(i)) ans++;
    }
    return ans;
}
bool map[210][210];
int main()
{
    int i,j,cases=0;
    int u,v;
    while(~scanf("%d%d%d",&n1,&n2,&m) && !(n1==0 && n2==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        memset(map,0,sizeof(map));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            map[u][v]=1;
        }
        for(i=1;i<=n1;i++)
            for(j=1;j<=n2;j++)
            {
                if(!map[i][j]) add(i,n1+j);
            }
        printf("Case %d: %d\n",++cases,n1+n2-xyl());


    }
    return 0;
}

hdoj4160 Dolls
一个盒子只能装一个，so。。可以想到最小路径覆盖，一条路径的起始点不就是一个裸露在外的盒子吗

#include<stdio.h>
#include<string.h>
#define maxn 510
#define maxe 150010
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[2*maxn];
int n,m,cnt;
int match[2*maxn];
bool use[maxn];
int a[510],b[510],c[510];
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            match[cur]=v;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=n+1;i<=n+n;i++)
    {
        memset(use,0,sizeof(use));
        if(match[i]) continue;
        if(dfs(i)) ans++;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n) && n)
    {
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
            scanf("%d%d%d",&a[i],&b[i],&c[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(i==j) continue;
                if(a[i]>a[j] && b[i]>b[j] && c[i]>c[j])
                    add(n+i,j);
            }
        printf("%d\n",n-xyl());
    }
    return 0;
}

hdoj4185
经典最大匹配。。

#include<stdio.h>
#include<string.h>
#define maxn 360000
#define maxe 10000000
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n,m,cnt;
int match[maxn];
bool use[maxn];
char map[610][610];
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=n && map[x][y]=='#') return 1;
    return 0;
}
int index(int x,int y)
{
    return (x-1)*n+y;
}
inline  void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;match[cur]=v;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if((i+j)&1 || match[index(i,j)]) continue;
            for(int k=1;k<=n*n;k++) use[k]=0;
            if(dfs(index(i,j))) ans++;
        }
    return ans;
}
int main()
{
    int i,j;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);getchar();
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                scanf("%c",&map[i][j]);
            getchar();
        }
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if((i+j)&1 || map[i][j]=='.') continue;
                int u=index(i,j);
                if(judge(i-1,j)) add(u,index(i-1,j));
                if(judge(i+1,j)) add(u,index(i+1,j));
                if(judge(i,j-1)) add(u,index(i,j-1));
                if(judge(i,j+1)) add(u,index(i,j+1));
            }
        printf("Case %d: %d\n",++cases,xyl());
    }
    return 0;
}

hdoj2413 Against Mammoths
题意：给出n1个h类星球，n2个a类星球，给出每个星球初始的飞船数量。给出每个星球造船速度p个/年，任意一个h类星球到任意一个a类星球的时间（年），现在要从h类星球派船征服a类星球，一个h类星球最多只能征服一个a类星球，且一个a类星球只能被一个h类星球征服。问征服所有a类星球最少需要多少时间，如果不能全部征服，输出IMPOSSIBLE
（如果从h类的i星派出x个飞船，到达a类的j星时，j星球有y个飞船，如果x>=y，h赢，否则a赢)
思路：二分时间，建立二分图，注意分两种情况讨论：
（1）当i的速率小于j时，那么“条件是不利的”，这时候造船越久越吃亏，所以对于h类星球的人，最优策略是一开始就出发派出该星所有飞船，如果这样还不能打败j星，则肯定不能打败，不建边
（2）除了（1）的情况，则二分给出的时间全用上看下能否打败，能则建边
ps:注意要用long long，太大也不行，会溢出，wa好多次。。

#include<stdio.h>
#include<string.h>
#define maxn 500+10
#define maxe 62500+10
typedef long long ll;
typedef struct Edge{
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int n1,n2,m,cnt;
int match[maxn];
bool use[maxn];
inline void add(int u,int v)
{
    edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
bool dfs(int cur)
{
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(use[v]) continue;
        use[v]=1;
        if(!match[v] || dfs(match[v]))
        {
            match[v]=cur;
            match[cur]=v;
            return 1;
        }
    }
    return 0;
}
int xyl()
{
    int ans=0;
    memset(match,0,sizeof(match));
    for(int i=1;i<=n1;i++)
    {
        if(match[i]) continue;
        memset(use,0,sizeof(use));
        if(dfs(i)) ans++;
    }
    return ans;
}
ll init[3][300],rate[3][300],map[300][300];
ll bsearch(ll l,ll r)
{
    ll m;
    int i,j;
    bool flag=0;
    while(l<=r)
    {
        m=l+(r-l)/2;
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=n1;i++)
            for(j=1;j<=n2;j++)
            {
                if(map[i][j]>m) continue;
                if(rate[1][i]<rate[2][j])
                {
                    ll numh=init[1][i];
                    ll numa=init[2][j]+map[i][j]*rate[2][j];
                    if(numh>=numa) add(i,n1+j);
                    continue;
                }
                ll numa=init[2][j]+m*rate[2][j];
                ll numh=init[1][i]+(m-map[i][j])*rate[1][i];
                if(numa>numh) continue;
                add(i,n1+j);
            }
        if(xyl()==n2) {flag=1;r=m-1;}
        else l=m+1;
    }
    if(flag) return l;
    else return -1;
}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n1,&n2) && !(n1==0 && n2==0))
    {
        for(i=1;i<=n1;i++)
            scanf("%I64d%I64d",&init[1][i],&rate[1][i]);
        for(i=1;i<=n2;i++)
            scanf("%I64d%I64d",&init[2][i],&rate[2][i]);
        for(i=1;i<=n1;i++)
            for(j=1;j<=n2;j++)
                scanf("%I64d",&map[i][j]);
        ll ans=bsearch(0,1000000000000LL);
        if(ans==-1) printf("IMPOSSIBLE\n");
        else printf("%I64d\n",ans);




    }
    return 0;
}

除了x[1]以外，其他x[]都是通过t[]数组转移的，so，显然x数组的值是在c数组中选的。
分情况：
（1）m<=0 显然无解
（2）若c数组中全是2：<1>那么如果m是奇数，无解.<2>m是偶数，有解
（3）若c数组中有1：第一个x选1，然后扩展，直到x数组的和>=m,由于x数组元素的值只可能是1或2，so，最终的和要么等于m，要么等于m+1，如果是等于m+1,只要去掉第一个1，从把x[2]的值作为x[1]扩展x数组即可。

#include<stdio.h>
#include<string.h>
int main()
{
    int n,q,tmp;
    int i,j;
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&tmp);
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&tmp);
            if(tmp==1) flag=1;
        }
        for(i=1;i<=q;i++)
        {
            scanf("%d",&tmp);
            if((tmp&1 && !flag) || tmp<=0)
                printf("NO\n");
            else
                printf("YES\n");
        }

    }

    return 0;
}

还是比较简单的题
思路；看到n的范围10^18，第一反应lg级别算法，然后发现时递推式，瞬间想到矩阵，既然是矩阵，自然是要推出aibi，然后很自然的会去想aibi有哪些组成部分推出来的呢，于是就会去把a和b的递推式左右分别乘乘一下。但是求的是所有aibi的和，简单，矩阵加一阶用来存储后面的aibi加起来的和即可。

#include<stdio.h>
#include<string.h>
#define mod 1000000007
typedef __int64 ll;
typedef struct Mat{
    ll m[8][8];
}Mat;
Mat per;
void init()
{
    int i,j;
    for(i=1;i<=5;i++)
        for(j=1;j<=5;j++)
            if(i==j) per.m[i][j]=1;
            else per.m[i][j]=0;
    return;
}
Mat multi(Mat a,Mat b)
{
    Mat ans;
    int i,j,t;
    for(i=1;i<=5;i++)
        for(j=1;j<=5;j++)
        {
            ll tmp=0;
            for(t=1;t<=5;t++)
                tmp=(tmp+a.m[i][t]*b.m[t][j])%mod;
            ans.m[i][j]=tmp%mod;
        }
    return ans;
}
Mat power(Mat a,ll k)
{
    Mat p=a,ans=per;
    while(k)
    {
        if(k&1)
        {
            k--;
            ans=multi(ans,p);
        }
        else
        {
            k/=2;
            p=multi(p,p);
        }
    }
    return ans;
}
Mat multi2(Mat a,Mat b)
{
    Mat ans;
    int i,j,t;
    for(i=1;i<=1;i++)
        for(j=1;j<=5;j++)
        {
            ll tmp=0;
            for(t=1;t<=5;t++)
                tmp=(tmp+a.m[i][t]*b.m[t][j])%mod;
            ans.m[i][j]=tmp%mod;
        }
    return ans;
}
int main()
{
    ll n,a0,b0,ax,ay,bx,by;
    int i,j;
    init();
    while(scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d",&n,&a0,&ax,&ay,&b0,&bx,&by)!=EOF)
    {
        Mat tmp;
        tmp.m[1][1]=1;tmp.m[1][2]=0;tmp.m[1][3]=0;tmp.m[1][4]=0;tmp.m[1][5]=0;
        tmp.m[2][1]=1;tmp.m[2][2]=(ax*bx)%mod;tmp.m[2][3]=0;tmp.m[2][4]=0;tmp.m[2][5]=0;
        tmp.m[3][1]=0;tmp.m[3][2]=ax*by%mod;tmp.m[3][3]=ax%mod;tmp.m[3][4]=0;tmp.m[3][5]=0;
        tmp.m[4][1]=0;tmp.m[4][2]=ay*bx%mod;tmp.m[4][3]=0;tmp.m[4][4]=bx%mod;tmp.m[4][5]=0;
        tmp.m[5][1]=0;tmp.m[5][2]=ay*by%mod;tmp.m[5][3]=ay%mod;tmp.m[5][4]=by%mod;tmp.m[5][5]=1;
        Mat tmp2=power(tmp,n);
        Mat sr;
        sr.m[1][1]=0;sr.m[1][2]=a0*b0%mod;sr.m[1][3]=a0%mod;sr.m[1][4]=b0%mod;sr.m[1][5]=1;
        Mat ans=multi2(sr,tmp2);
        printf("%I64d\n",ans.m[1][1]%mod);
    }
    return 0;
}

前段时间空间和域名超期了，刷的几个专题都没记录，忘了一大半。。
hdoj：
2242考研路茫茫——空调教室 双联通缩点+树形DP
2460Network 边双连通
3849By Recognizing These Guys, We Find Social Networks Useful 双连通求桥
3896Greatest TC 双连通
4005 The war 边双连通
3394Railway 双连通求块

poj：
3694 Network 边双连通 (同hdu2460)
3177 Redundant Paths 构造边双连通
3352 Road Construction 构造边双连通
2942 Knights of the Round Table (点双连通经典题)
1515 Street Directions (无向图改有向图)
1438 One-way Traffic (混合图改有向图)

zoj
2682 People like People

njust1738 TWO NODES
2013南京邀请赛的B题，当时还没学双连通，一头雾水，完全无想法，直接导致我们队与奖牌失之交臂。现在再来看这道题，实乃水题也。。看下时限自己算一下可以很容易得出枚举的思路
思路：假设我们已经删去了第一个点，那么在剩下的图中，要使连通分量数目最大，那么必然是删除割点。但是第一次删的点则不一定是割点，首先原图可能根本没割点，其次，第一次删去的点的不同会导致剩下的图中的点是否是割点具有不确定性。到这里我们得出第一次删去的不一定是割点，第二次删去的一定是割点（存在割点的情况下）。
因而，思路就是枚举第一次删去哪个点。那么对于第二次删去的点，应该删哪个割点呢，可以发现：一个割点在几个块中，这个割点就可以把图分成几个点双连通分量，所以就是要求出每个割点出现在不同的块中的次数，遍历一次所有块中的割点即可。
上面的讨论都是在删去第一个点之后剩余的图中存在割点这个前提下的，那么如果剩余的图中没有割点呢？此时会出现一个trick（被坑了2次），如果你认为这种情况下图是一个或多个双连通分量，直接是双连通分量数，那就悲剧了。正确做法是分情况讨论：如果剩余的图一条边都没有，那么由于一个连通量只有单个点，这个点不会被视为割点（手工模拟下tarjan你就明白了），所以此时删去第二个点，连通量不是不变，而是减一。另一种情况就是存在多于1个点的双联通分量的情况，删去第二个点的时候分量数不变。
其实这题还有一种情况，就是删去第一个点之后的图中是两点一边（+单个独立点）的情况，像下面这样：

按照tarjan的流程可以发现，两个点a,b中第一个被访问的点a会成为割点，这个割点只在这两个点组成的分量里。那么计算时，删去这个割点，这个分量由一个分量变成一个num[a]个分量（num[a]表示割点a出现在几个双连通分量中），即删去两个点之后的最大连通量数是：删去第一个点后的分量数-1+num[a]=删去第一个点后的分量数。答案恰好是正确的，所以这种情况其实不用特殊考虑。

/******************************
一条边唯一属于一个块，桥及其两个端点构成一个块
******************************/
#include<stdio.h>
#include<string.h>
#include<stack>
#include<vector>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=5000+10;
const int maxe=20000+10;
typedef struct Edge
{
    int from,to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dfn[maxn],low[maxn];
int belong[maxn];//每个点属于哪个block，注意：割点的belong[]没有意义
int id,cnt,dcc,n,m;
bool cut[maxn];
stack<Edge> s;
vector<int> block[maxn];
int num[maxn];
inline int min(int a,int b){return a<b?a:b;}
void add(int u,int v)
{
    edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void dfs(int cur,int fa,int x,int &has)
{
    dfn[cur]=low[cur]=++id;
    int son=0;
    bool flag=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==x) continue;
        if(v==fa && flag){flag=0;continue;}
        has=1;
        if(!dfn[v])
        {
            s.push(edge[i]);
            son++;
            dfs(v,cur,x,has);
            low[cur]=min(low[cur],low[v]);
            if(low[v]>=dfn[cur])
            {
                cut[cur]=1;
                dcc++;
                if(!block[dcc].empty())block[dcc].clear();
                while(1)
                {
                    Edge x=s.top();s.pop();
                    if(belong[x.from]!=dcc){block[dcc].push_back(x.from);belong[x.from]=dcc;}
                    if(belong[x.to]!=dcc){block[dcc].push_back(x.to);belong[x.to]=dcc;}
                    if(x.from==cur && x.to==v) break;
                }
            }
        }
        else if(dfn[cur]>dfn[v])
        {
            s.push(edge[i]);
            low[cur]=min(low[cur],dfn[v]);
        }
    }
    if(fa==-1 && son>=2) cut[cur]=1;
    return;
}
int tarjan(int x)
{
    int i,j;
    int tmp=0,has=0;
    id=dcc=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    memset(cut,0,sizeof(cut));
    memset(num,0,sizeof(num));
    for(i=1;i<=n;i++)
        if(!dfn[i] && i!=x)
        {
            dfs(i,-1,x,has);
            tmp++;
        }
    for(i=1;i<=dcc;i++)
    {
        for(j=0;j<block[i].size();j++)
            if(cut[block[i][j]]) num[block[i][j]]++;
    }
    int ans=1;
    for(i=1;i<=n;i++)
        if(i!=x && cut[i] && num[i]>ans) {ans=num[i];}
    if(has==0) return tmp-1;
    return tmp-1+ans;
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        int u,v;
        cnt=0;memset(head,-1,sizeof(head));
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            u++;v++;
            if(u==v) continue;
            add(u,v);add(v,u);
        }
        int ans=1;
        for(i=1;i<=n;i++)
        {
            int tmp=tarjan(i);
            if(tmp>ans) ans=tmp;
        }
        printf("%d\n",ans);
    }
    return 0;
}