首页 > ACM题库 > HDU-杭电 > HDU 3718-Similarity-二分图-[解题报告]HOJ
2015
02-21

HDU 3718-Similarity-二分图-[解题报告]HOJ

Similarity

问题描述 :

When we were children, we were always asked to do the classification homework. For example, we were given words {Tiger, Panda, Potato, Dog, Tomato, Pea, Apple, Pear, Orange, Mango} and we were required to classify these words into three groups. As you know, the correct classification was {Tiger, Panda, Dog}, {Potato, Tomato, Pea} and {Apple, Pear, Orange, Mango}. We can represent this classification with a mapping sequence{A,A,B,A,B,B,C,C,C,C}, and it means Tiger, Panda, Dog belong to group A, Potato, Tomato, Pea are in the group B, and Apple, Pear, Orange, Mango are in the group C.
But the LABEL of group doesn’t make sense and the LABEL is just used to indicate different groups. So the representations {P,P,O,P,O,O,Q,Q,Q,Q} and {E,E,F,E,F,F,W,W,W,W} are equivalent to the original mapping sequence. However, the representations {A,A,A,A,B,B,C,C,C,C} and
{D,D,D,D,D,D,G,G,G,G} are not equivalent.

Rescue

The pupils in class submit their mapping sequences and the teacher should read and grade the homework. The teacher grades the homework by calculating the maximum similarity between pupils’ mapping sequences and the answer sequence. The definition of similarity is as follow.

Similarity(S, T) = sum(Si == Ti) / L
L = Length(S) = Length(T), i = 1, 2,… L,
where sum(Si == Ti) indicates the total number of equal labels in corresponding positions. The maximum similarity means the maximum similarities between S and all equivalent sequences of T, where S is the answer and fixed. Now given all sequences submitted by pupils and the answer sequence, you should calculate the sequences’ maximum similarity.

输入:

The input contains multiple test cases. The first line is the total number of cases T (T < 15). The following are T blocks. Each block indicates a case. A case begins with three numbers n (0 < n < 10000), k (0 < k < 27), m (0 < m < 30), which are the total number of objects, groups, and students in the class. The next line consists of n labels and each label is in the range [A...Z]. You can assume that the number of different labels in the sequence is exactly k. This sequence represents the answer. The following are m lines, each line contains n labels and each label also is in the range [A...Z]. These m lines represent the m pupils’ answer sequences. You can assume that the number of different labels in each sequence doesn’t exceed k.

输出:

The input contains multiple test cases. The first line is the total number of cases T (T < 15). The following are T blocks. Each block indicates a case. A case begins with three numbers n (0 < n < 10000), k (0 < k < 27), m (0 < m < 30), which are the total number of objects, groups, and students in the class. The next line consists of n labels and each label is in the range [A...Z]. You can assume that the number of different labels in the sequence is exactly k. This sequence represents the answer. The following are m lines, each line contains n labels and each label also is in the range [A...Z]. These m lines represent the m pupils’ answer sequences. You can assume that the number of different labels in each sequence doesn’t exceed k.

样例输入:

2
10 3 3
A A B A B B C C C C
F F E F E E D D D D
X X X Y Y Y Y Z Z Z
S T R S T R S T R S
3 2 2
A B A
C D C
F F E

样例输出:

1.0000
0.7000
0.5000
1.0000
0.6667

一个二分图最大匹配的题;

匈牙利算法不熟;

建了个模,用最小费用最大流解决了

 #include <iostream>
 #include <cstring>
 #define INF 9999999
 #include <cstdio>
 #include <queue>
 #include <vector>
 #include<algorithm>
 using namespace std;
 #define maxn 6100
 
 struct  edge
 {
     int from,to,cap,flow,cost;
 };
 struct MCMF
 {
     int n,m,s,t;
     vector<edge>edges;
     vector<int>G[maxn];
     int inq[maxn];
     int d[maxn];
     int p[maxn];
     int a[maxn];
     void init(int n)
     {
         this->n=n;
         for(int i=0; i<n; i++)
             G[i].clear();
         edges.clear();
     }
     void addedge(int from,int to,int cap,int cost)
     {
         edges.push_back((edge){from,to,cap,0,cost});
         edges.push_back((edge){to,from,0,0,-cost});
         m=edges.size();
         G[from].push_back(m-2);
         G[to].push_back(m-1);
     }
 
     bool bellman(int s,int t,int &flow,int &cost)
     {
         for(int i=0; i<n; i++)d[i]=INF;
         memset(inq,0,sizeof(inq));
         d[s]=0;
         inq[s]=1;
         p[s]=0;
         a[s]=INF;
 
         queue<int>Q;
         Q.push(s);
         while(!Q.empty())
         {
             int u = Q.front();
             Q.pop();
             inq[u] = 0;
             for(int i = 0; i < G[u].size(); i++)
             {
                 edge& e = edges[G[u][i]];
                 if(e.cap > e.flow && d[e.to] > d[u] + e.cost)
                 {
                     d[e.to] = d[u] + e.cost;
                     p[e.to] = G[u][i];
                     a[e.to] = min(a[u], e.cap - e.flow);
                     if(!inq[e.to])
                     {
                         Q.push(e.to);
                         inq[e.to] = 1;
                     }
                 }
             }
         }
         if(d[t] == INF) return false;
         flow += a[t];
         cost += d[t]*a[t];
         int u = t;
         while(u != s)
         {
             edges[p[u]].flow += a[t];
             edges[p[u]^1].flow -= a[t];
             u = edges[p[u]].from;
         }
         return true;
     }
     int Mincost(int s, int t)
     {
         int flow = 0, cost = 0;
         while(bellman(s, t, flow, cost));
         return cost;
     }
 };
 int n;
 int k,m;
 char s2[10200],s1[10200];
 int cur[30][30];
 int tot[30];
 void first_solve()
 {
     memset(cur,0,sizeof(cur));
     memset(tot,0,sizeof(tot));
     for(int i=1; i<=n; i++)
     {
         int k1=s1[i]-'A'+1;
         int k2=s2[i]-'A'+1;
         tot[k1]++;
         cur[k1][k2]++;
     }
 }
 MCMF solve;
 int main()
 {
     int t;
     int st=0;
     int final=201;
     scanf("%d",&t);
     while(t--)
     {
         scanf("%d%d%d",&n,&k,&m);
         for(int i=1; i<=n; i++)
         {
             char s[5];
             scanf("%s",s);
             s1[i]=s[0];
         }
         for(int d=1; d<=m; d++)
         {
             solve.init(final+1);
             for(int j=1; j<=n; j++)
             {
                 char s[5];
                 scanf("%s",s);
                 s2[j]=s[0];
             }
             first_solve();
             for(int i=1; i<=26; i++)
                 solve.addedge(st,i,1,0);
             for(int i=1; i<=26; i++)
             {
                 for(int j=1; j<=26; j++)
                 {
                     int cnt=26+j;
                     if (cur[i][j])
                         solve.addedge(i,cnt,1,tot[i]-cur[i][j]);
                     else solve.addedge(i,cnt,1,tot[i]);
                 }
             }
             for(int i=1;i<=26;i++)solve.addedge(i+26,final,1,0);
             int ans=n-solve.Mincost(st,final);
             printf("%.4lf\n",(double)ans/(double)n);
         }
     }
     return 0;
 }

 

参考:http://www.cnblogs.com/yours1103/archive/2013/11/06/3411417.html


  1. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }