Proud Merchants

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 925    Accepted Submission(s): 368

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN=5005;
int dp[MAXN];
struct Node
{
    int p,q,v;
}node[505];
bool cmp(Node a,Node b)
{
    return  (a.q-a.p)<(b.q-b.p);
}    
int main()
{
    int n,m;
    int i,j;
    int p,q,v;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<=m;i++)
          dp[i]=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d%d",&node[i].p,&node[i].q,&node[i].v);
        }    
        sort(node,node+n,cmp);
        for(i=0;i<n;i++)
        {
            for(j=m;j>=node[i].p;j--)
            {
                if(j>=node[i].q)
                  dp[j]=max(dp[j],dp[j-node[i].p]+node[i].v);
            }    
        }
        int ans=0;
        for(i=1;i<=m;i++)
          if(ans<dp[i])  ans=dp[i];
        printf("%d\n",ans);
              
    }    
    return 0;
}  

过山车

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2978    Accepted Submission(s): 1222

#include<stdio.h>
#include<string.h>
const int MAXN=510;
int uN,vN;  //u,v数目
int g[MAXN][MAXN];//编号是0~n-1的 
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }  
    return false;  
}    
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    } 
    return res;   
}  
int main()
{
    int k;
    int u,v;
    while(scanf("%d",&k),k)
    {
        scanf("%d%d",&uN,&vN);
        memset(g,0,sizeof(g));
        while(k--)
        {
            scanf("%d%d",&u,&v);
            g[u][v]=1;
        } 
        printf("%d\n",hungary());   
    }  
    return 0;  
}  

前面的内容来源于：http://www.cnblogs.com/phinecos/archive/2009/09/11/1564975.html

引用原文：

在数据结构课关于栈的这一章中，我们都学过用“模2取余法”来将一个10进制数转换为一个二进制数，进而可以推广到“模n取余法”，经其转换为n进制（n任意指定）。

确实，这是一个很基础的题目，可你是否想过如果这个10进制数是一个大数（其位数可能上千位，此时用一般数据类型肯定是会溢出的），那么这个问题又如何来求解呢？

当然，也许你会说很简单嘛，自己写一个大数类（当然至少要写一个大数除法才行），或者你用的是Java这种现代化语言，就更轻松了，直接用BigInteger这样的大数类就可以来表示一个大数，进而用书上教的方法来实现。

但是，真的需要用到大数类吗？事实上，“杀鸡焉用牛刀“，我们在纸上模拟一番上述运算后就可以发现，只要做一些小小的改进，就可以在不使用大数的情况下，也可以通过“模n取余”的原理来实现大数的进制转换的。（当然，整体的思想仍然是“模n取余”原理！！！）。

举个简单的例子，就比如说把10进制数12转换为2进制形式，书上的方法可以用下图来表示

按照 “先余为低位，后余为高位“这条铁律，其结果为1100.

这是书上教我们的常规思路（可惜按这个的话，大数是没法考虑的，因为假如这里不是12，而是一个1000位的大数，由于是是对大数的整体进行取余运算，不使用大数类及其除法操作，又如何得以进行呢？），可我们的目的是不使用大数类，那么现在我们就来换一个视角来看这个问题，12是一个十位数，十位上是1，个位上是2，按照我们正常的思维来看，这个计算应该是下面这样的：

那么我们发现在第一轮运算时，十位上的1作为被除数，2作为除数，得到的商是0，余数是1(可以断言只考虑当前这一个数位的计算，余数或是0，或是1，若是1的话，则进入下一数位（这里即对个位进行运算）时，要用1乘上进制（这里是10）再加上下一个数位上的值（这里是2）)，即得到运算进入个位时被除数是12，除数是2，得到的商是6，余数是0。第一轮运算的结果是商是06，余数是0.

进入第二轮运算，则上一轮的商6（这里首先要去掉前面多余的0）变成本轮的被除数，如此下去，即可得到每轮的余数。

推广开来，如果被除数是一个1000位的大数，例如“12343435154324123……342314324343”

那么我们照样可以从第一个数位开始逐位考虑，比如第一位是1（作为被除数），2是除数，得到的商是0，余数是1，然后是第二个数位2，由于上一位留下了余数1，则此时被除数应该是1*10+2 = 12,所以得到的商是6，余数是0，即运算到此时的商是06，然后是第三个数位3，由于上一个数位留下的余数是0，所以此时被除数就是3，。。。如此下去就完成第一轮的运算，

这一轮完毕后，需要把得到的商变成下一轮的被除数，继续上述的运算，直到被除数为0才停止。

下面给出了一个示例代码，展示了如何将一个10进制的大数转换为其二进制形式，仅供参考：

#include <stdio.h>
#include <string.h>

char str[1000];//输入字符串
int start[1000],ans[1000],res[1000]; //被除数，商，余数

//转换前后的进制
const int oldBase = 10;
const int newBase = 2;

void change()
{//各个数位还原为数字形式
    int i,len = strlen(str);
    start[0] = len;
    for(i=1;i<= len;i++)
    {
        if(str[i-1] >= '0' && str[i-1] <= '9')
        {
            start[i] = str[i-1] - '0';
        }
    } 
}

void solve()
{
    memset(res,0,sizeof(res));//余数初始化为空
    int y,i,j;
    //模n取余法，(总体规律是先余为低位，后余为高位)
    while(start[0] >= 1)
    {//只要被除数仍然大于等于1，那就继续“模2取余”
        y=0;
        i=1;
        ans[0]=start[0];
        //
        while(i <= start[0])
        {
            y = y * oldBase + start[i];
            ans[i++] = y/newBase;
            y %= newBase; 
        }
        res[++res[0]] = y;//这一轮运算得到的余数
        i = 1;
        //找到下一轮商的起始处
        while((i<=ans[0]) && (ans[i]==0)) i++;
        //清除这一轮使用的被除数
        memset(start,0,sizeof(start));
        //本轮得到的商变为下一轮的被除数
        for(j = i;j <= ans[0];j++)
            start[++start[0]] = ans[j]; 
        memset(ans,0,sizeof(ans)); //清除这一轮的商，为下一轮运算做准备
    } 
}

void output()
{//从高位到低位逆序输出
    int i;
    for(i = res[0];i >= 1;--i)
    {  
        printf("%d",res[i]);
    }
    printf("\n"); 
}

int main()
{
    scanf("%s",str);
    change();
    solve();
    output();
    return 0;
}

个人根据POJ1220，总结高精度的N进制转换模板如下：

/*
高精度进制转换 
把oldBase 进制的数转化为newBase 进制的数输出。
调用方法，输入str, oldBase newBase.
change();
solve();
output();
也可以修改output(),使符合要求，或者存入另外一个字符数组，备用 
*/
#include<stdio.h>
#include<string.h>
#defien MAXSIZE 1000
char str[MAXSIZE];//输入字符串
int start[MAXSIZE],ans[MAXSIZE],res[MAXSIZE];//被除数，商，余数
int oleBasw,newBase;//转换前后的进制

//单个字符得到数字
int getNum(char c)//这里进制字符是先数字，后大写字母，后小写字母的 
{
    if(c>='0'&&c<='9') return c-'0';//数字 
    if(c>='A'&&c>='Z') return c-'A'+10;//大写字母 
    return c-'a'+36;//小写字母 
}    
//数字得到字符
char getChar(int i)
{
    if(i>=0&&i<=9)return i+'0';
    if(i>=10&&i<=35)return i-'10'+'A';
    return i-36+'a';
}     
void change()//把输入的字符串的各个数位还原为数字形式
{
    int i;
    start[0]=strlen(str);//数组的0位存的是数组长度
    for(i=1;i<=start[0];i++)
        start[i]=getNum(str[i-1]); 
}    
void solve()
{
    memset(res,0,sizeof(res));//余数位初始化为空
    int y,i,j;
    while(start[0]>=1) 
    {
        y=0;i=1;
        ans[0]=start[0];
        while(i<=start[0])
        {
            y=y*oldBase+start[i];
            ans[i++]=y/newBase;
            y%=newBase;
        }    
        res[++res[0]]=y;//这一轮得到的余数
        i=1;//找下一轮商的起始处，去掉前面的0
        while(i<=ans[0]&&ans[i]==0) i++;
        memset(start,0,sizeof(start));
        for(j=i;j<ans[0];j++)
           start[++start[0]]=ans[j];
        memset(ans,0,sizeof(ans)); 
    }    
}  
void output()//从高位到低位逆序输出 
{
    int i;
    for(i=res[0];i>=1;i--)
        printf("%d",getChar(res[i]));
    printf("\n");
} 

Description

Input

Output

Sample Input

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

Sample Output

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

Source

/*
高精度进制转换 
把oldBase 进制的数转化为newBase 进制的数输出。
调用方法，输入str, oldBase newBase.
change();
solve();
output();
也可以修改output(),使符合要求，或者存入另外一个字符数组，备用 
*/
#include<stdio.h>
#include<string.h>
#define MAXSIZE 1000
char str[MAXSIZE];//输入字符串
int start[MAXSIZE],ans[MAXSIZE],res[MAXSIZE];//被除数，商，余数
int oldBase,newBase;//转换前后的进制

//单个字符得到数字
int getNum(char c)//这里进制字符是先数字，后大写字母，后小写字母的 
{
    if(c>='0'&&c<='9') return c-'0';//数字 
    if(c>='A'&&c<='Z') return c-'A'+10;//大写字母 
    return c-'a'+36;//小写字母 
}    
//数字得到字符
char getChar(int i)
{
    if(i>=0&&i<=9)return i+'0';
    if(i>=10&&i<=35)return i-10+'A';
    return i-36+'a';
}     
void change()//把输入的字符串的各个数位还原为数字形式
{
    int i;
    start[0]=strlen(str);//数组的0位存的是数组长度
    for(i=1;i<=start[0];i++)
        start[i]=getNum(str[i-1]); 
}    
void solve()
{
    memset(res,0,sizeof(res));//余数位初始化为空
    int y,i,j;
    while(start[0]>=1) 
    {
        y=0;i=1;
        ans[0]=start[0];
        while(i<=start[0])
        {
            y=y*oldBase+start[i];
            ans[i++]=y/newBase;
            y%=newBase;
        }    
        res[++res[0]]=y;//这一轮得到的余数
        i=1;//找下一轮商的起始处，去掉前面的0
        while(i<=ans[0]&&ans[i]==0) i++;
        memset(start,0,sizeof(start));
        for(j=i;j<=ans[0];j++)
           start[++start[0]]=ans[j];
        memset(ans,0,sizeof(ans)); 
    }    
}  
void output()//从高位到低位逆序输出 
{
    int i;
    printf("%d %s\n",oldBase,str);
    printf("%d ",newBase);
    for(i=res[0];i>=1;i--)
        printf("%c",getChar(res[i]));
    printf("\n\n");
} 
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %d %s",&oldBase,&newBase,str);
        change();
        solve();
        output();
    }    
    return 0;
}    

一、最大匹配——匈牙利算法

/****************************************************
二分图匹配（匈牙利算法的DFS实现）
INIT：g[][]两边定点划分的情况
CALL:res=hungary();输出最大匹配数
优点：适于稠密图，DFS找增广路快，实现简洁易于理解
时间复杂度:O(VE);
****************************************************/
const int MAXN=1000;
int uN,vN;  //u,v数目
int g[MAXN][MAXN];//编号是0~n-1的 
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    int v;
    for(v=0;v<vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }  
    return false;  
}    
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=0;u<uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    } 
    return res;   
}     

简单例子：

HDU 2063过山车

#include<stdio.h>

#include<string.h>

const int MAXN=510;

int uN,vN;  //u,v数目

int g[MAXN][MAXN];//编号是0~n-1的

int linker[MAXN];

bool used[MAXN];

bool dfs(int u)

{

    int v;

    for(v=1;v<=vN;v++)

        if(g[u][v]&&!used[v])

        {

            used[v]=true;

            if(linker[v]==-1||dfs(linker[v]))

            {

                linker[v]=u;

                return true;

            }   

        } 

    return false; 

}   

int hungary()

{

    int res=0;

    int u;

    memset(linker,-1,sizeof(linker));

    for(u=1;u<=uN;u++)

    {

        memset(used,0,sizeof(used));

        if(dfs(u))  res++;

    }

    return res;  

} 

int main()

{

    int k;

    int u,v;

    while(scanf("%d",&k),k)

    {

        scanf("%d%d",&uN,&vN);

        memset(g,0,sizeof(g));

        while(k--)

        {

            scanf("%d%d",&u,&v);

            g[u][v]=1;

        }

        printf("%d\n",hungary());  

    } 

    return 0; 

} 

例：HDU 1045 Fire Net

/*

HDU 1045

*/

#include<stdio.h>

#include<string.h>

#include<iostream>

using namespace std;

int uN,vN;

int g[20][20];

int linker[20];

bool used[20];

char map[5][5];

int mapr[5][5];

int mapl[5][5];

bool dfs(int u)

{

    int v;

    for(v=1;v<=vN;v++)

        if(g[u][v]&&!used[v])

        {

            used[v]=true;

            if(linker[v]==-1||dfs(linker[v]))

            {

                linker[v]=u;

                return true;

            }   

        }

    return false;  

} 

int hungary()

{

    int res=0;

    int u;

    memset(linker,-1,sizeof(linker));

    for(u=1;u<=uN;u++)

    {

        memset(used,0,sizeof(used));

        if(dfs(u))  res++;

    }  

    return res;

} 

int main()

{

    int i,j,n;

    while(scanf("%d",&n),n)

    {

        memset(mapl,0,sizeof(mapl));

        memset(mapr,0,sizeof(mapr));

        memset(g,0,sizeof(g));

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

           for(j=1;j<=n;j++)

           {

               cin>>map[i][j];

               if(map[i][j]=='X')

                  mapl[i][j]=mapr[i][j]=-1;

           } 

           int p1=0;

           uN=0;vN=0;

           //给行编号

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

              for(j=1;j<=n;j++)

              {

                  while(mapr[i][j]==-1&&j<=n)

                      j++;

                  p1++;

                  while(mapr[i][j]!=-1&&j<=n)

                  {

                      mapr[i][j]=p1;

                      if(uN<p1)  uN=p1;

                      j++;

                  }   

              }

          int p2=0;

          //给列编号

          for(j=1;j<=n;j++)

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

             {

                 while(mapl[i][j]==-1&&i<=n)

                      i++;

                  p2++;

                  while(mapl[i][j]!=-1&&i<=n)

                  {

                      mapl[i][j]=p2;

                      if(vN<p2)  vN=p2;

                      i++;

                  }   

             }

         //建图

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

            for(j=1;j<=n;j++)

            {

                if(mapr[i][j]!=-1&&mapl[i][j]!=-1)

                  g[mapr[i][j]][mapl[i][j]]=1;

            }

         printf("%d\n",hungary());           

    }

    return 0;   

}

Fire Net

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2349    Accepted Submission(s): 1342

Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.



Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

/*
HDU 1045
*/
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int uN,vN;
int g[20][20];
int linker[20];
bool used[20];
char map[5][5];
int mapr[5][5];
int mapl[5][5];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        } 
    return false;   
}  
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    }   
    return res; 
}  
int main()
{
    int i,j,n;
    while(scanf("%d",&n),n)
    {
        memset(mapl,0,sizeof(mapl));
        memset(mapr,0,sizeof(mapr));
        memset(g,0,sizeof(g));
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
           {
               cin>>map[i][j];
               if(map[i][j]=='X')
                  mapl[i][j]=mapr[i][j]=-1;
           }  
           int p1=0;
           uN=0;vN=0;
           //给行编号 
           for(i=1;i<=n;i++)
              for(j=1;j<=n;j++)
              {
                  while(mapr[i][j]==-1&&j<=n)
                      j++;
                  p1++;
                  while(mapr[i][j]!=-1&&j<=n)
                  {
                      mapr[i][j]=p1;
                      if(uN<p1)  uN=p1;
                      j++;
                  }    
              } 
          int p2=0;
          //给列编号 
          for(j=1;j<=n;j++)
             for(i=1;i<=n;i++)
             {
                 while(mapl[i][j]==-1&&i<=n)
                      i++;
                  p2++;
                  while(mapl[i][j]!=-1&&i<=n)
                  {
                      mapl[i][j]=p2;
                      if(vN<p2)  vN=p2;
                      i++;
                  }    
             }
         //建图 
         for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(mapr[i][j]!=-1&&mapl[i][j]!=-1)
                  g[mapr[i][j]][mapl[i][j]]=1;
            }
         printf("%d\n",hungary());            
    } 
    return 0;   
} 

/*
HDU 1045(暴搜方法） 
*/
#include<stdio.h>
using namespace std;

char map[5][5];
int maxnum;
int n;
bool Build(int row,int col)
{
    int i,j;
    for(i=row;i>=0;i--)
    {
        if(map[i][col]=='O') return false;
        if(map[i][col]=='X') break;
    }    
    for(j=col;j>=0;j--)
    {
        if(map[row][j]=='O') return false;
        if(map[row][j]=='X') break;
    } 
    return true;   
}    
void dfs(int i,int num)
{
    int row,col;
    if(i==n*n)
    {
        if(num>maxnum) maxnum=num;
        return ;
    } 
    else
    {
        row=i/n;
        col=i%n;
        if(map[row][col]=='.'&&Build(row,col))
        {
            map[row][col]='O';
            dfs(i+1,num+1);
            map[row][col]='.';
        }    
        dfs(i+1,num);
    }       
}
int main()
{
    int i;
    while(scanf("%d",&n),n)
    {
        maxnum=0;
        for(i=0;i<n;i++)
          scanf("%s",&map[i]);
        dfs(0,0);
        printf("%d\n",maxnum);
    }
    return 0;    
}    

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2444

题意：

        有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。

分析：

先是要判断是否为二部图，然后求最大匹配。

这里的程序hungary()用vector实现

/*
HDU 2444 The Accomodation of Students

*/
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define MAXN 202
vector<int>EV[MAXN];
int linker[MAXN];
bool used[MAXN];
int uN;
int matchs[MAXN],cnt[MAXN];
bool dfs(int u)
{
    int i;
    for(i=0;i<EV[u].size();i++)
    {
        int v=EV[u][i];
        if(!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }    
    }
    return false;    
}   
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,false,sizeof(used));
        if(dfs(u))  res++;
    }
    return res;    
}  
bool judge(int x,int y)
{
    int i;
    for(i=0;i<EV[x].size();i++)
    {
        if(cnt[EV[x][i]]==0)
        {
            cnt[EV[x][i]]=-1*y;
            matchs[EV[x][i]]=true;
            if(!judge(EV[x][i],-1*y)) return false;
        }   
        else if(cnt[EV[x][i]]==y)  return false; 
    }    
    return true;
}    
bool matched()
{
    int i;
    memset(matchs,false,sizeof(matchs));
    for(i=1;i<=uN;i++)
    {
        if(EV[i].size()&&!matchs[i])
        {
            memset(cnt,0,sizeof(cnt));
            cnt[i]=-1;
            matchs[i]=true;
            if(!judge(i,-1)) return false;
        }    
    }
    return true;    
}     
int main()
{
    int m;
    int i;
    int u,v;
    while(scanf("%d%d",&uN,&m)!=EOF)
    {
        for(i=1;i<=uN;i++)
          if(EV[i].size())  EV[i].clear();
        while(m--)
        {
            scanf("%d%d",&u,&v);
            EV[u].push_back(v);
            EV[v].push_back(u);
        }    
     
         if(matched())
                  printf("%d\n",hungary()/2);
         else  printf("No\n");    
    } 
    return 0;
}

题目大意：

有p个课程和n个学生，每个学生可以自由选择课程（0到p个），现在要建立一个委员会，问是否能找到每个课程都有学生代表的集合，一个学生只能代表一个课程

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1083

简单的二分匹配，用匈牙利算法就可以，主要是练习模板，固定方法解题！

程序：

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 305
int g[MAXN][MAXN];
int uN,vN;
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }
    return false;    
}    
int hungary()
{
    int res=0,u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    }  
    return res;  
}   
int main()
{
    int u,v;
    int T,i,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&uN,&vN);
        memset(g,0,sizeof(g));
        for(u=1;u<=uN;u++)
        {
            scanf("%d",&n);
            while(n--)
            {
                scanf("%d",&v);
                g[u][v]=1;
            }    
        } 
        if(uN==hungary())  printf("YES\n");
        else  printf("NO\n");   
    }  
    return 0;  
} 

不好意思，感觉太简单了就没有加注释！！！匈牙利算法，详解可以看我前面几遍关于二分匹配的文章！

棋盘游戏

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)

Total Submission(s) : 5   Accepted Submission(s) : 4

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。
所以现在Gardon想让小希来解决一个更难的问题，在保证尽量多的“车”的前提下，棋盘里有些格子是可以避开的，也就是说，不在这些格子上放车，也可以保证尽量多的“车”被放下。但是某些格子若不放子，就无法保证放尽量多的“车”，这样的格子被称做重要点。Gardon想让小希算出有多少个这样的重要点，你能解决这个问题么？

Input

Output

Sample Input

3 3 4
1 2
1 3
2 1
2 2
3 3 4
1 2
1 3
2 1
3 2

Sample Output

Board 1 have 0 important blanks for 2 chessmen.
Board 2 have 3 important blanks for 3 chessmen.

Author

Source

#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 105
int g[MAXN][MAXN];
int uN,vN;
int linker[MAXN];
bool used[MAXN];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }
    return false;    
}    
int hungary()
{
    int res=0,u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    }  
    return res;  
}  
int main()
{
    int K,x,y;
    int i,j;
    int ans;
    int iCase=0;
    while(scanf("%d%d%d",&uN,&vN,&K)!=EOF)
    {
        iCase++;
        memset(g,0,sizeof(g));
        while(K--)
        {
            scanf("%d%d",&x,&y);
            g[x][y]=1;
        }  
        ans=hungary();
        int cnt=0;
        for(i=1;i<=uN;i++)
           for(j=1;j<=vN;j++)
           {
               if(g[i][j]==1)
               {
                   g[i][j]=0;
                   if(ans>hungary()) cnt++;
                   g[i][j]=1;
               }    
           }
        printf("Board %d have %d important blanks for %d chessmen.\n",iCase,cnt,ans);     
    } 
    return 0;   
    
}   

Swap

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 459    Accepted Submission(s): 129
Special Judge

#include<stdio.h>
#include<string.h>
const int MAXN=105;
int uN,vN;  //u,v数目
int g[MAXN][MAXN];//编号是0~n-1的 
int linker[MAXN];
bool used[MAXN];
int a[10000],b[10000];
bool dfs(int u)
{
    int v;
    for(v=1;v<=vN;v++)
        if(g[u][v]&&!used[v])
        {
            used[v]=true;
            if(linker[v]==-1||dfs(linker[v]))
            {
                linker[v]=u;
                return true;
            }    
        }  
    return false;  
}    
int hungary()
{
    int res=0;
    int u;
    memset(linker,-1,sizeof(linker));
    for(u=1;u<=uN;u++)
    {
        memset(used,0,sizeof(used));
        if(dfs(u))  res++;
    } 
    return res;   
}     
int main()
{
    int N;
    int i,j,u,v;
    while(scanf("%d",&N)!=EOF)
    {
        uN=vN=N;
        for(i=1;i<=uN;i++)
          for(j=1;j<=vN;j++)
            scanf("%d",&g[i][j]);
        int ans=hungary();
        //printf("%d\n",ans);
        if(ans<N){printf("-1\n");continue;}
        int res=0;
        for(i=1;i<=uN;i++)
        {
            for(j=i;j<=vN;j++)
               if(linker[j]==i) break;
            if(j!=i)
            {
                a[res]=i;b[res++]=j;
                int t=linker[i];linker[i]=linker[j];linker[j]=t;
            }    
        } 
        printf("%d\n",res);
        for(i=0;i<res;i++)
          printf("C %d %d\n",a[i],b[i]);
           
        
    } 
    return 0;   
}