計(jì)算二分圖的算法有網(wǎng)絡(luò)流算法和匈牙利算法（目前就知道這兩種），其中匈牙利算法是比較巧妙的，具體過(guò)程如下（轉(zhuǎn)自組合數(shù)學(xué)）：
令g=（x,*,y）是一個(gè)二分圖，其中x={x1,x2
},y={y1,y2,.}.令m為g中的任意匹配。
1。將x的所有不與m的邊關(guān)聯(lián)的頂點(diǎn)表上￥，并稱(chēng)所有的頂點(diǎn)為未掃描的。轉(zhuǎn)到2。
2。如果在上一步?jīng)]有新的標(biāo)記加到x的頂點(diǎn)上，則停，否則 ，轉(zhuǎn)3
3。當(dāng)存在x被標(biāo)記但未被掃描的頂點(diǎn)時(shí)，選擇一個(gè)被標(biāo)記但未被掃描的x的頂點(diǎn)，比如xi，用（xi）標(biāo)
記y 的所有頂點(diǎn)，這些頂點(diǎn)被不屬于m且尚未標(biāo)記的邊連到xi。
現(xiàn)在頂點(diǎn)xi 是被掃描的。如果不存在被標(biāo)記但未被掃描的頂點(diǎn)，轉(zhuǎn)4。
4。如果在步驟3沒(méi)有新的標(biāo)記被標(biāo)記到y(tǒng)的頂點(diǎn)上，則停，否則轉(zhuǎn)5。
5。當(dāng)存在y被標(biāo)記但未被掃描的頂點(diǎn)時(shí)。選擇y的一個(gè)被標(biāo)記但未被掃描的頂點(diǎn)，比如yj，
用（yj）標(biāo)記x的頂點(diǎn)，這些頂點(diǎn)被屬于m且尚未標(biāo)記的邊連到y(tǒng)j。現(xiàn)在，頂點(diǎn)yj是被掃描的。
如果不存在被標(biāo)記但未被掃描的頂點(diǎn)則轉(zhuǎn)道2。
由于每一個(gè)頂點(diǎn)最多被標(biāo)記一次且由于每一個(gè)頂點(diǎn)最多被掃描一次，本匹配算法在有限步內(nèi)終止。
匈牙利算法思想:
今天剛看了二分匹配..以前的沒(méi)怎么好好想過(guò)，今天看了下，其實(shí)很簡(jiǎn)單..就是不斷找增廣路
過(guò)程...有x,y兩個(gè)集合，對(duì)x這個(gè)集合每個(gè)點(diǎn)遍歷一遍，遍歷當(dāng)前點(diǎn)時(shí)，如果y中有個(gè)未匹配的點(diǎn)
，直接跳出,ans++,如果在y中所有和x的點(diǎn)都匹配過(guò)，則對(duì)這些點(diǎn)再找，如果有其他的路，則
更新，ans++，如果沒(méi)，則把當(dāng)前的點(diǎn)置為匹配的點(diǎn)，ans不變..x++;
相關(guān)題目:
http://acm.hdu.edu.cn/showproblem.php?pid=1151http://acm.hdu.edu.cn/showproblem.php?pid=1068http://acm.hdu.edu.cn/showproblem.php?pid=1150http://acm.hdu.edu.cn/showproblem.php?pid=1281http://acm.hdu.edu.cn/showproblem.php?pid=1498http://acm.hdu.edu.cn/showproblem.php?pid=1528http://acm.hdu.edu.cn/showproblem.php?pid=1507相關(guān)知識(shí):
二分圖的最小頂點(diǎn)覆蓋=二分圖的最大匹配數(shù)
二分圖的最大獨(dú)立集=頂點(diǎn)數(shù)-二分圖的最大匹配數(shù)
二分圖的最小路徑覆蓋=頂點(diǎn)數(shù)-二分圖的最大匹配數(shù)
http://acm.hdu.edu.cn/showproblem.php?pid=1530(赤裸裸的最大團(tuán))
http://acm.zju.edu.cn/show_problem.php?pid=3008
1 #include <iostream>
2 #include <vector>
3 #include <cmath>
4
5 using namespace std;
6 class Num
7 {
8 public:
9 void factorization(){
10 //n==1特殊處理
11
12 //
13 //n>1
14 int i=0;
15 for(i=0;n%2==0&&n>1;n/=2,i++);
16 if(i>0){
17 prime.push_back(2);
18 num.push_back(i);
19 }
20
21 int t=0,j;
22 for(i=3;i<=n;i+=2){
23 for(j=0;n%i==0&&n>1;n/=i,j++);
24 if(j>0){
25 prime.push_back(i);
26 num.push_back(j);
27 }
28 }
29 return;
30 }
31 Num(int x=0):n(x){
32 prime.clear();
33 num.clear();
34 }
35 vector<int> prime,num;
36 int n;
37 };
38 Num p;
39 int n,m,ans;
40 void dfs(int i,unsigned long long val)
41 {
42 unsigned long long tt=val;
43 unsigned long long t=1;
44 for(int j=0;i<p.num.size()&&j<=p.num[i]*m;j++){
45 val*=t;
46 if(val<=n&&i==p.num.size()-1){
47 ans++;
48 //return;
49 }
50 if(val<=n&&i+1<p.num.size()){
51 dfs(i+1,val);
52 }
53 if(val>n)return;
54 t*=p.prime[i];
55 val=tt;
56 }
57 return ;
58 }
59 int main()
60 {
61 while(scanf("%d%d",&n,&m)!=EOF){
62 if(n==1){
63 printf("1\n");
64 continue;
65 }
66 ans=0;
67 p.n=n;
68 p.num.clear();
69 p.prime.clear();
70 p.factorization();
71 dfs(0,1);
72 printf("%d\n",ans);
73 }
74 return 0;
75 }
1 #include <iostream>
2 #include <algorithm>
3 #include <vector>
4
5 using namespace std;
6 struct Node
7 {
8 int xi,yi;
9 Node(int x=0,int y=0):xi(x),yi(y){};
10 };
11 bool op1(const Node& a,const Node& b)
12 {
13 if(a.xi==b.xi)return a.yi<b.yi;
14 return a.xi<b.xi;
15 }
16 bool op2(const Node& a,const Node& b)
17 {
18 if(a.yi==b.yi)return a.xi<b.xi;
19 return a.yi<b.yi;
20 };
21
22 int marx[10005];
23
24 vector<Node> vecx,vecy;
25 int main()
26 {
27 int c;
28 scanf("%d",&c);
29 while(c--){
30 vecx.clear();
31 vecy.clear();
32 int n,m;
33 scanf("%d%d",&n,&m);
34 int x,y;
35 for(int i=0;i<n;i++){
36 scanf("%d%d",&x,&y);
37 Node tmp(x,y);
38 ++marx[x];
39 vecx.push_back(tmp);
40 vecy.push_back(tmp);
41 }
42
43 sort(vecx.begin(),vecx.end(),op1);
44 sort(vecy.begin(),vecy.end(),op2);
45
46 int ans=0x7fffffff;
47 int start=0,cnt,tt,end=0;
48 for(int i=0;i<n;++i){
49 for(int j=i;j<n;++j){
50 start=0;
51 end=-1;
52 cnt=0;
53 tt=0;
54 for(start=0;start<n&&end<n;){
55 if(cnt<m){
56 end++;
57 if(end==n)break;
58 if(vecx[end].yi<=vecy[j].yi&&vecx[end].yi>=vecy[i].yi)cnt++;
59 }
60 else{
61 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi){
62 int lenx=abs(vecx[end].xi-vecx[start].xi)+2;
63 int leny=abs(vecy[i].yi-vecy[j].yi)+2;
64 if(lenx*leny<ans)ans=lenx*leny;
65 }
66 if(vecx[start].yi<=vecy[j].yi&&vecx[start].yi>=vecy[i].yi)cnt--;
67 start++;
68 }
69 }
70 }
71 }
72 printf("%d\n",ans); //start++
73 }
74 return 0;
75 }
實(shí)力不夠...繼續(xù)努力...
http://acm.pku.edu.cn/JudgeOnline/problem?id=3670
1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5 const int N=30005;
6 int dp1[N];
7 int dp2[N];
8 int dp3[N];
9 int d1[N];
10 int d2[N];
11 int main()
12 {
13 int n;
14 while(cin>>n){
15 int num;
16 memset(dp1,0,sizeof(dp1));
17 memset(dp2,0,sizeof(dp2));
18 memset(dp3,0,sizeof(dp3));
19 for(int i=0;i<n;i++){
20 cin>>d1[i];
21 d2[n-i-1]=d1[i];
22 }
23 switch(d1[0]){
24 case 1:
25 dp1[0]=0,dp2[0]=1,dp3[0]=1;
26 break;
27 case 2:
28 dp1[0]=1,dp2[0]=0,dp3[0]=1;
29 break;
30 case 3:
31 dp1[0]=1,dp2[0]=1,dp3[0]=0;
32 break;
33 }
34
35 for(int i=1;i<n;i++){
36 switch(d1[i]){
37 case 1:
38 dp1[i]=dp1[i-1];
39 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
40 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
41 break;
42 case 2:
43 dp1[i]=dp1[i-1]+1;
44 dp2[i]=min(dp1[i-1],dp2[i-1]);
45 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
46 break;
47 case 3:
48 dp1[i]=dp1[i-1]+1;
49 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
50 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]));
51 break;
52 }
53 }
54 int ans=0x7fffffff;
55 if(ans>dp1[n-1])ans=dp1[n-1];
56 if(ans>dp2[n-1])ans=dp2[n-1];
57 if(ans>dp3[n-1])ans=dp3[n-1];
58
59 switch(d2[0]){
60 case 1:
61 dp1[0]=0,dp2[0]=1,dp3[0]=1;
62 break;
63 case 2:
64 dp1[0]=1,dp2[0]=0,dp3[0]=1;
65 break;
66 case 3:
67 dp1[0]=1,dp2[0]=1,dp3[0]=0;
68 break;
69 }
70
71 for(int i=1;i<n;i++){
72 switch(d2[i]){
73 case 1:
74 dp1[i]=dp1[i-1];
75 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
76 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
77 break;
78 case 2:
79 dp1[i]=dp1[i-1]+1;
80 dp2[i]=min(dp1[i-1],dp2[i-1]);
81 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]))+1;
82 break;
83 case 3:
84 dp1[i]=dp1[i-1]+1;
85 dp2[i]=min(dp1[i-1],dp2[i-1])+1;
86 dp3[i]=min(dp1[i-1],min(dp2[i-1],dp3[i-1]));
87 break;
88 }
89 }
90
91 if(ans>dp1[n-1])ans=dp1[n-1];
92 if(ans>dp2[n-1])ans=dp2[n-1];
93 if(ans>dp3[n-1])ans=dp3[n-1];
94
95 cout<<ans<<endl;
96 }
97 return 0;
98 }
99