首页 > 代码库 > POJ 3308 最少点集覆盖

POJ 3308 最少点集覆盖

题意:和Uva 11419 类似。

首先最少点集覆盖 = 最大匹配。

我们可以在 S 和行 的边 不是1,有了权值,但是题意要求的是乘积最小,那么可以用 log(a*b) = loga + logb 转换,那么权值就是logr ,logc;

最大匹配 = 最大流(最大流一定经过最小割,最小割=最大流)。那么题目就转换为求最大流了。

 

但是,这个题目很流氓,vector的邻接表超时,数组模拟的G++ WA,C++ AC.

技术分享
#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>#include <cmath>using namespace std;/*const double inf = 1000000.0;const int maxn = 100;int dblcmp(double d) {    if(fabs(d)<1e-5)        return 1;    return 0;}struct Edge {    int from,to;    double cap,flow;};struct Dinic{    int n,m,s,t;    vector<Edge> edge;    vector<int> G[maxn];    bool vis[maxn];    int d[maxn];    int cur[maxn];    void init()    {        for(int i=0;i<maxn;i++)            G[i].clear();        edge.clear();        memset(d,0,sizeof(d));        memset(vis,0,sizeof(vis));        memset(cur,0,sizeof(cur));    }    void AddEdge (int from,int to,double cap)    {        edge.push_back((Edge){from,to,cap,0});        edge.push_back((Edge){to,from,0,0});        m = edge.size();        G[from].push_back(m-2);        G[to].push_back(m-1);    }    bool BFS()    {        memset(vis,0,sizeof(vis));        queue<int> Q;        Q.push(s);        d[s] = 0;        vis[s] = 1;        while(!Q.empty())        {            int x = Q.front();            Q.pop();            for(int i=0; i<G[x].size(); i++)            {                Edge & e = edge[G[x][i]];                if(!vis[e.to]&&e.cap>e.flow)                {                    vis[e.to] = 1;                    d[e.to] = d[x] + 1;                    Q.push(e.to);                }            }        }        return vis[t];    }    double DFS(int x,double a)    {        if(x==t||dblcmp(a)) return a;        double flow = 0,f;        for(int & i = cur[x]; i<G[x].size(); i++)        {            Edge & e = edge[G[x][i]];            if(d[x] + 1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)            {                e.flow +=f;                edge[G[x][i]^1].flow -=f;                flow +=f;                a-=f;                if(dblcmp(a)) break;            }        }        return flow;    }    double Maxflow (int s,int t) {        this->s = s;this->t = t;        double flow = 0;        while(BFS()) {            memset(cur,0,sizeof(cur));            flow+=DFS(s,inf);        }        return flow;    }}sol;*/const int N = 105;const double inf = 1000000.0;struct Edge{    int s,e,next;    double v;}edge[15*N];int n,e_num,head[N],d[N],sp,tp;void AddEdge(int a,int b,double c){    edge[e_num].s=a; edge[e_num].e=b; edge[e_num].v=c;    edge[e_num].next=head[a]; head[a]=e_num++;    edge[e_num].s=b; edge[e_num].e=a; edge[e_num].v=0.0;    edge[e_num].next=head[b]; head[b]=e_num++;}int bfs(){    queue <int> q;    memset(d,-1,sizeof(d));    d[sp]=0;    q.push(sp);    while(!q.empty()){        int cur=q.front();        q.pop();        for(int i=head[cur];i!=-1;i=edge[i].next){            int u=edge[i].e;            if(d[u]==-1 && edge[i].v>0){//没有标记,且可行流大于0                d[u]=d[cur]+1;                q.push(u);            }        }    }    return d[tp] != -1;//汇点是否成功标号,也就是说是否找到增广路}double dfs(int a,double b){//a为起点    double r=0;    if(a==tp)return b;    for(int i=head[a];i!=-1 && r<b;i=edge[i].next){        int u=edge[i].e;        if(edge[i].v>0 && d[u]==d[a]+1){            double x=min(edge[i].v,b-r);            x=dfs(u,x);            r+=x;            edge[i].v-=x;            edge[i^1].v+=x;        }    }    if(!r)d[a]=-2;    return r;}double dinic(int sp,int tp){    double total=0.0,t;    while(bfs()){        while(t=dfs(sp,inf))        total+=t;    }    return total;}int main(){    int t;    scanf("%d",&t);    int i,m,l,a,b;    double row[N],col[N];    while(t--) {        /*        //sol.init();        int m,n,l;        scanf("%d%d%d",&m,&n,&l);        sp = 0,tp=m+n+1;        e_num=0;        memset(head,-1,sizeof(head));        for(int i=1;i<=m;i++) {            double r;            scanf("%lf",&r);            //sol.AddEdge(s,i,log(r));            AddEdge(sp,i,log(r));        }        for(int i=1;i<=n;i++) {            double c;            scanf("%lf",&c);            //sol.AddEdge(i+m,t,log(c));            AddEdge(i+m,tp,log(c));        }        for(int i=0;i<l;i++) {            int u,v;            scanf("%d%d",&u,&v);            v+=m;            //sol.AddEdge(u,v,inf);            AddEdge(u,v,inf);        }        //double ans = sol.Maxflow(s,t);        double ans = dinic(sp,tp);        printf("%.4lf\n",exp(ans));        */        scanf("%d%d%d",&n,&m,&l);        for(i=1;i<=n;i++)            scanf("%lf",&row[i]);        for(i=1;i<=m;i++)            scanf("%lf",&col[i]);        e_num=0;        memset(head,-1,sizeof(head));        sp=0; tp=n+m+1;        for(i=1;i<=n;i++)            AddEdge(sp,i,log(row[i]));        for(i=1;i<=m;i++)            AddEdge(n+i,tp,log(col[i]));        for(i=1;i<=l;i++){            scanf("%d%d",&a,&b);            AddEdge(a,n+b,inf);        }        printf("%.4lf\n",exp(dinic(sp,tp)));    }    return 0;}
View Code

 

POJ 3308 最少点集覆盖