学步园

1.飞行员配对方案问题 二分匹配

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=110;

int n,m,match[NN];
bool mp[NN][NN],used[NN];

bool dfs(int u)
{
    for (int v=1; v<=m; v++) if (mp[u][v])
    {
        if (used[v]) continue;
        used[v]=1;
        if (match[v]==-1 || dfs(match[v]))
        {
            match[v]=u;
            return true;
        }
    }
    return false;
}

void hungary()
{
    memset(match,-1,sizeof(match));

    int cnt=0;
    for (int i=1; i<=n; i++)
    {
        memset(used,0,sizeof(used));
        if (dfs(i)) cnt++;
    }

    if (cnt==0) puts("No Solution!");
    else
    {
        printf("%d\n",cnt);
        for (int i=1; i<=m; i++) if (match[i]!=-1)
        {
            printf("%d %d\n",match[i],i);
        }
    }
}

int main()
{
    int u,v;

    scanf("%d%d",&n,&m);
    memset(mp,0,sizeof(mp));
    while (scanf("%d%d",&u,&v)==2 && u!=-1 && v!=-1)
    {
        mp[u][v]=1;
    }

    hungary();

    return 0;
}

2.太空飞行计划问题 最大权闭包

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=888;
const int MM=888888;
const int INF=888888888;

int S,T,NV,en,head[NN];
struct Edge
{
    int u,v,f,next;
    Edge() {}
    Edge(int _u,int _v,int _f,int _next):u(_u),v(_v),f(_f),next(_next) {}
} e[MM];
void add(int u,int v,int f)
{
    e[en]=Edge(u,v,f,head[u]);
    head[u]=en++;
    e[en]=Edge(v,u,0,head[v]);
    head[v]=en++;
}

int gap[NN],dis[NN],cur[NN],pre[NN];
int sap()
{
    int ret=0;
    for (int i=0; i<NV; i++)
    {
        cur[i]=head[i];
        dis[i]=gap[i]=0;
    }

    int aug=0;
    int u=pre[S]=S;
    gap[0]=NV;
    while (dis[S]<NV)
    {
loop:
        for (int &i=cur[u]; i!=-1; i=e[i].next)
        {
            int v=e[i].v;
            if (e[i].f && dis[u]==dis[v]+1)
            {
                if (e[i].f<aug) aug=e[i].f;
                pre[v]=u;
                u=v;
                if (u==T)
                {
                    ret+=aug;
                    for (u=pre[u]; v!=S; v=u,u=pre[u])
                    {
                        e[cur[u]].f-=aug;
                        e[cur[u]^1].f+=aug;
                    }
                    aug=INF;
                }
                goto loop;
            }
        }

        int min_dis=NV;
        for (int i=head[u]; i!=-1; i=e[i].next)
        {
            int v=e[i].v;
            if (e[i].f>0 && dis[v]<min_dis)
            {
                min_dis=dis[v];
                cur[u]=i;
            }
        }

        if (--gap[dis[u]]==0) break;
        gap[dis[u]=min_dis+1]++;
        u=pre[u];
    }

    return ret;
}

bool f[NN];
void dfs(int u)
{
    f[u]=true;
    for (int i=head[u]; i!=-1; i=e[i].next)
    {
        if (e[i].f && !f[e[i].v]) dfs(e[i].v);
    }
}

vector<int> vec[NN];
int main()
{
    int m,n,w,x;
    char c;

    en=0;
    memset(head,-1,sizeof(head));

    scanf("%d%d",&m,&n);
    S=0;
    T=m+n+1;
    NV=T+1;

    int sum=0;
    for (int i=1; i<=m; i++)
    {
        scanf("%d",&w);
        sum+=w;
        add(S,i,w);
        while (1)
        {
            while (c=getchar(),!isdigit(c) && c!='\n');
            if (c=='\n') break;
            x=c-'0';
            c=getchar();
            while (isdigit(c)) x=x*10+c-'0',c=getchar();
            vec[i].push_back(x);
            if (c=='\n') break;
        }
    }
    for (int i=1; i<=n; i++)
    {
        scanf("%d",&w);
        add(i+m,T,w);
    }
    for (int i=1; i<=m; i++)
        for (int j=0; j!=vec[i].size(); j++) add(i,vec[i][j]+m,INF);

    int ans=sum-sap();
    memset(f,0,sizeof(f));
    dfs(S);

    bool flag=0;
    for (int i=1; i<=m; i++) if (f[i])
    {
        if (!flag) flag=1;
        else       printf(" ");
        printf("%d",i);
    }
    puts("");
    flag=0;
    for (int i=1; i<=n; i++) if (f[i+m])
    {
        if (!flag) flag=1;
        else       printf(" ");
        printf("%d",i);
    }
    printf("\n%d\n",ans);

    return 0;
}

3.软件补丁问题 最短路dij

#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;

const int NN=110;
const int MM=1100000;

int n,m,w[NN],b1[NN],b2[NN],f1[NN],f2[NN];
int dis[MM];
bool vis[MM];

struct node{
    int v;
    node () {}
    node(int _v): v(_v) {}
    bool operator <(const node a)const{
        return dis[a.v]<dis[v];
    }
};

bool match(int x,int i)
{
    for (int j=0; j<n; j++)
    {
        if ( (b1[i]&(1<<j)) && !(x&(1<<j)) ) return 0;
        if ( (b2[i]&(1<<j)) && (x&(1<<j)) ) return 0;
    }
    return 1;
}

int patch(int x,int i)
{
    int y=x;
    for (int j=0; j<n; j++)
    {
        if (f1[i]&(1<<j)) y|=1<<j;
        if (f2[i]&(1<<j)) y&=~(1<<j);
    }

    return y;
}

priority_queue<node> q;
int dij()
{
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));

    dis[(1<<n)-1]=0;
    q.push(node((1<<n)-1));

    while (!q.empty())
    {
        int u=q.top().v; q.pop();

        if (u==0) return dis[u];
        if (vis[u]) continue;
        vis[u]=true;
        //printf("%d %d\n",u,dis[u]);
        for (int i=1; i<=m; i++) if (match(u,i))
        {
            int v=patch(u,i);//printf("v: %d,%d\n",v,i);
            if (dis[v]>dis[u]+w[i])
            {
                dis[v]=dis[u]+w[i];
                q.push(node(v));
            }
        }
    }

    return 0;
}

char s1[32],s2[32];
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
    {
        scanf("%d%s%s",&w[i],s1,s2);
        b1[i]=b2[i]=0;
        for (int j=0; j<n; j++)
        {
            if (s1[j]=='+') b1[i]|=1<<j;
            if (s1[j]=='-') b2[i]|=1<<j;
        }
        f1[i]=f2[i]=0;
        for (int j=0; j<n; j++)
        {
            if (s2[j]=='+') f1[i]|=1<<j;
            if (s2[j]=='-') f2[i]|=1<<j;
        }
    }
    printf("%d\n",dij());

    return 0;
}

待续。。。