计算二分图的算法有网络流算法和匈牙利算法（目前就知道这两种），其中匈牙利算法是比较巧妙的，具体过程如下（转自组合数学）：
令g=（x,*,y）是一个二分图，其中x={x1,x2
},y={y1,y2,.}.令m为g中的任意匹配。
1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到2。
2。如果在上一步没有新的标记加到x的顶点上，则停，否则 ，转3
3。当存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标
记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。
现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，转4。
4。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。
5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如yj，
用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。现在，顶点yj是被扫描的。
如果不存在被标记但未被扫描的顶点则转道2。
由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。
匈牙利算法思想:
今天刚看了二分匹配..以前的没怎么好好想过，今天看了下，其实很简单..就是不断找增广路
过程...有x,y两个集合，对x这个集合每个点遍历一遍，遍历当前点时，如果y中有个未匹配的点
，直接跳出,ans++,如果在y中所有和x的点都匹配过，则对这些点再找，如果有其他的路，则
更新，ans++，如果没，则把当前的点置为匹配的点，ans不变..x++;
相关题目:
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相关知识:
二分图的最小顶点覆盖=二分图的最大匹配数
二分图的最大独立集=顶点数-二分图的最大匹配数
二分图的最小路径覆盖=顶点数-二分图的最大匹配数
posted @
2008-07-31 15:56 小果子 阅读(688) |
评论 (0) |
编辑 收藏http://acm.hdu.edu.cn/showproblem.php?pid=1530(赤裸裸的最大团)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1419
pku1419解析:
本题是给定一个无向图G,对顶点进行染色（0，1），使相邻的两个点不同时为1(黑色),因为n>=100,直接暴搜的话复杂度为2^100,(据说也能过，未尝试),换思路，因为相邻的点不能同时为1，所以只要找出最大的一个集合，使该集合内的点都没有边，集合内点的个数就是答案,就是求最大独立集...而最大独立集=G' 的最大团...所以转化为求最大团......
posted @
2008-07-31 13:03 小果子 阅读(788) |
评论 (0) |
编辑 收藏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 }
posted @
2008-07-28 20:58 小果子 阅读(363) |
评论 (0) |
编辑 收藏 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 }
实力不够...继续努力...
posted @
2008-07-28 17:43 小果子 阅读(247) |
评论 (0) |
编辑 收藏 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
posted @
2008-07-25 15:27 小果子 阅读(211) |
评论 (0) |
编辑 收藏