HDU

Hold Your Hand

Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 169 Accepted Submission(s): 38

Problem Description

She walks in beauty, like the night of cloudless climes and starry skies. And all that's best of dark and bright, meet in her aspect and her eyes. Thus mellow'd to that tender light, which heaven to gaudy day denies. Fang Fang says she is afraid of dark.

``Never fear, I will hold your hand," I reply.

Fang Fang says she hates some

Input

The input contains several test cases. The first line of the input is a single integer

Output

For each test case, you should output the minimum cost of IQ as a unit, or ``-1" if Cupid could not help me.

Sample Input

8 7

0 1 2 3 4 5 6 7

P 000001 1

P 0000000 1

S 10 1

S 11 1

S 00 1

S 01 1

P 0000001 3

Sample Output

Case #1: 4

题意转化一下就是要割断所有的8位二进制。

将前缀插入以S为根的字典树，后缀插入以T为根的字典树。val保存最小的w。

一个前缀对应着割断所有包含这个前缀的二进制，后缀类似。

然后把两颗树的对应叶子结点相连跑最小割。

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int sigma_size = 2,maxnds = (256*8*2+56)*2;
int S,T;

struct Edge
{
    int v,cap,nxt;
};
#define PB push_back
vector<Edge> edges;
int head[maxnds];
inline void AddEdge(int u,int v,int c)
{
    edges.PB({v,c,head[u]});
    head[u] = edges.size()-1;
    edges.PB({u,0,head[v]});
    head[v] = edges.size()-1;
}

bool vis[maxnds];
int lv[maxnds],cur[maxnds];
bool bfs()
{
    memset(vis,0,sizeof(vis));
    queue<int> q; q.push(S); lv[S] = 1;
    vis[S] = true;
    while(q.size()){
        int u = q.front(); q.pop();
        for(int i = head[u]; ~i; i = edges[i].nxt){
            Edge &e = edges[i];
            if(!vis[e.v] && e.cap>0){
                vis[e.v] = true;
                lv[e.v] = lv[u]+1;
                q.push(e.v);
            }
        }
    }
    return vis[T];
}

int aug(int u,int a)
{
    if(u == T||!a) return a;
    int flow = 0,f;
    for(int &i = cur[u]; ~i; i = edges[i].nxt){
        Edge &e = edges[i];
        if(lv[e.v] == lv[u]+1 && (f=aug(e.v,min(a,e.cap)))>0){
            e.cap -= f; edges[i^1].cap += f;
            flow += f; a -= f;
            if(!a) break;
        }
    }
    return flow;
}

int MaxFlow()
{
    int flow = 0;
    while(bfs()){
        memcpy(cur,head,sizeof(head));
        flow += aug(S,INF);
        if(flow >= INF) break;
    }
    return flow;
}

struct Node
{
    int ch[sigma_size],val;
    void init(){}
}nd[maxnds];
const int nil = 0;
int cnt;

inline int newNode()
{
    int i = ++cnt;
    memset(nd[i].ch,nil,sizeof(nd[i].ch));
    nd[i].val = INF;
    head[i] = -1;
    return i;
}


int add(int rt,char *s,int v = INF)
{
    int u = rt;
    for(int i = 0; s[i]; i++){
        int c = s[i]-'0';
        if(!nd[u].ch[c]){
            nd[u].ch[c] = newNode();
        }
        u = nd[u].ch[c];
    }
    nd[u].val = min(nd[u].val,v);
    return u;
}


bool flag;
void dfs(int u)
{
    for(int i = 0; i < sigma_size; i++){
        int v = nd[u].ch[i];
        if(v){
            int w = nd[v].val;
            if(flag){
                AddEdge(u,v,w);
            }else {
                AddEdge(v,u,w);
            }
            dfs(v);
        }
    }
}

int main()
{
    //freopen("in.txt","r",stdin);

    char s[10];
    int x[256+6];
    int Test; scanf("%d",&Test);
    for(int kas = 1; kas<= Test; kas++){
        edges.clear();
        cnt = 0;
        S = newNode(); T = newNode();

        int n,m; scanf("%d%d",&n,&m);
        for(int i = 0; i < n; i++){
            scanf("%d",x+i);
        }

        while(m--){
            char ch[2];
            int w; scanf("%s%s%d",ch,s,&w);
            if(*ch=='P'){
                add(S,s,w);
            }else {
                reverse(s,s+strlen(s));
                add(T,s,w);
            }
        }
        s[8] = '';
        for(int i = 0; i < n; i++){
            int t = x[i];
            for(int j = 0; j < 8; j++){
                s[j] = (t&1)+'0';
                t>>=1;
            }
            int v = add(T,s);
            reverse(s,s+8);
            AddEdge(add(S,s),v,INF);
        }
        flag = true;
        dfs(S);
        flag = false;
        dfs(T);
        printf("Case #%d: ",kas);
        int flow = MaxFlow();
        if(flow >= INF){
            puts("-1");
        }else printf("%d
",flow);
    }
    return 0;
}