首页 > 代码库 > 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;}
POJ 3308 最少点集覆盖
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。