首页 > 搜索 > DFS搜索 > hdu 2728 Copier Reduction-DFS-[解题报告]C++
2014
02-14

hdu 2728 Copier Reduction-DFS-[解题报告]C++

Copier Reduction

问题描述 :

What do you do if you need to copy a 560x400mm image onto a standard sheet of US letter-size paper (which is about 216x280mm), while keeping the image as large as possible? You can rotate the image 90 degrees (so that it is in "landscape" mode), then reduce it to 50% of its original size so that it is 200x280mm. Then it will fit on the paper without overlapping any edges. Your job is to solve this problem in general.

输入:

The input consists of one or more test cases, each of which is a single line containing four positive integers A, B, C, and D, separated by a space, representing an AxBmm image and a CxDmm piece of paper. All inputs will be less than one thousand. Following the test cases is a line containing four zeros that signals the end of the input.

输出:

The input consists of one or more test cases, each of which is a single line containing four positive integers A, B, C, and D, separated by a space, representing an AxBmm image and a CxDmm piece of paper. All inputs will be less than one thousand. Following the test cases is a line containing four zeros that signals the end of the input.

样例输入:

560 400 218 280
10 25 88 10
8 13 5 1
9 13 10 6
199 333 40 2
75 90 218 280
999 99 1 10
0 0 0 0

样例输出:

50%
100%
12%
66%
1%
100%
1%

http://acm.hdu.edu.cn/showproblem.php?pid=3829

http://acm.hdu.edu.cn/showproblem.php?pid=2768

思路:以cat_lover和dog_lover把观众分为两个集合。只要两个集合内的人的选择有冲突,这两个顶点连接,边代表矛盾,然后求最大独立集。

       最大独立集 = 顶点数 – 最小顶点覆盖数(最大匹配数)

 

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<string>
#include<climits>
#include<cstdio>
#include<vector>
#include<utility>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define IN puts("in")
#define OUT puts("out")
#define FR(x) freopen(x,"r",stdin)
#define FW(x) freopen(x,"w",stdout)
#define MSET(x,y) memset(x,y,sizeof(x))
#define ST system("pause")
#define lowbit(x) (x)&(-x)
#define L(x) (x)<<1
#define R(x) ((x)<<1)^1
using namespace std;
const int maxn = 505;
char cat[maxn][2][5];
char dog[maxn][2][5];
struct nd{
        int v,next;
}edge[maxn*maxn];
int head[maxn],vis[maxn],to[maxn];
int ecnt,n,m,vv;
void add(int u,int v)
{
        edge[ecnt].v = v;
        edge[ecnt].next = head[u];
        head[u] = ecnt++;
}
void readin()
{
        int i,j,c,d,v;
        char str[2][5];
        scanf("%d %d %d",&c,&d,&v);
        vv = v;
        n = m = ecnt = 0;
        while(v--)
        {
                scanf("%s %s",str[0],str[1]);
                if(str[0][0]=='D'){
                        strcpy(dog[n][0],str[0]);
                        strcpy(dog[n][1],str[1]);
                        n++;
                }else{
                        strcpy(cat[m][0],str[0]);
                        strcpy(cat[m][1],str[1]);
                        m++;
                }
        }
        MSET(head,-1);
        for(i = 0; i < n; ++ i)
                for(j = 0; j < m; ++ j)
                        if(strcmp(dog[i][0],cat[j][1])==0||strcmp(dog[i][1],cat[j][0])==0)
                                add(i,j);
}
int dfs(int u)
{
        int i,v;
        for(i = head[u]; i != -1; i = edge[i].next)
        {
                v = edge[i].v;
                if(!vis[v]){
                        vis[v] = 1;
                        if(to[v]==-1||dfs(to[v])){
                                to[v] = u;
                                return 1;
                        }
                }
        }return 0;
}
void processing()
{
        int i,k = 0;
        MSET(to,-1);
        for(i = 0; i < n; ++ i){
                MSET(vis,0);
                k += dfs(i);
        }
        printf("%d\n",vv-k);
}
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
            readin();
            processing();
        }
        return 0;
}

 

 

 

解题转自:http://www.cnblogs.com/aigoruan/archive/2012/07/25/2608033.html


,
  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. if(j){
    int ans=a ;
    for(int x=j-1;x>=0;x–){
    if(!a ) break;
    ans=min(ans,a );
    sum+=ans;
    }
    }
    求解释,,dp的思路是什么呢?