首页 > 代码库 > oj1638
oj1638
分数规划,将边权改造;
第一次被卡精度,mmp
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define maxx 1000000000 #define ecp 1e-5 using namespace std; struct {int y,next,hh;double flow;}e[10000]; int lin[10000],len=0,re[10000]; int f=0; int hh[10000]; int read() { int k;cin>>k;return k; } void init(int x,int y,double fo,int id) { e[++len].next=lin[x];e[len].y=y;e[len].flow=fo;lin[x]=len,re[len]=len+1;e[len].hh=id; e[++len].next=lin[y];e[len].y=x;e[len].flow=fo;lin[y]=len;re[len]=len-1;e[len].hh=id; return ; } struct pp{int a,b;}sum[10000]; bool aaa(pp q,pp w) {return q.a>w.a||q.a==w.a&&q.b<w.b;} int st,n,ed,m; double zxc,xxx; int topx=0; int tot; int ans[100000]; int top=0; int a[100000],b[100000],c[100000]; int k[100000]; int rx1[10000],rx2[10000]; double rv1[10000],rv2[10000]; int q[100000],tail=0,head,level[1000]; bool makelevel() { memset(level,-1,sizeof(level)); head=0;tail=1; q[1]=st;level[st]=1; while(head++<tail) { int x=q[head]; for(int i=lin[x];i;i=e[i].next) { if(k[i]==1)continue; int y=e[i].y; if(e[i].flow>0&&level[y]==-1){level[y]=level[x]+1;q[++tail]=y;} } } return level[ed]!=-1; } double makeflow(int x,double flow) { if(x==ed)return flow; double axx=0,d=0; for(int i=lin[x];i&&axx<flow;i=e[i].next) { int y=e[i].y; if(k[i]==1)continue; if(level[y]==level[x]+1&&e[i].flow>0) { if(d=makeflow(y,min(flow-axx,e[i].flow))) { axx+=d; e[i].flow-=d; e[re[i]].flow+=d; } } } if(axx==0)level[x]=-1; return axx; } double dinic() { double ans=0; double d; while(makelevel()) while(d=makeflow(st,maxx)) ans+=d; return ans; } double build(double k) { double ansx=0; len=0; memset(re,0,sizeof(re)); memset(lin,0,sizeof(lin)); memset(e,0,sizeof(e)); for(int i=1;i<=m;i++) { double fo=1.0*c[i]-k; if(fo<0){ansx+=fo;if(f==1){ans[++top]=i;}} else {init(a[i],b[i],fo,i);} } return ansx; } void work1() { double left=0,right=1e10; double mid; while(left+1e-9<right) { mid=(left+right)/2; double g=build(mid); g+=dinic(); if(g>0)left=mid; else right=mid; } zxc=left; return ; } void rebuild() { for(int i=1;i<=len;i+=2)e[i].flow=e[re[i]].flow=1.0*(e[re[i]].flow+e[i].flow)/2; } void work2() { f=1; build(zxc); xxx=dinic(); rebuild(); double j=dinic(); for(int i=1;i<=len;i++) { sum[i].a=e[i].flow; sum[i].b=i; } sort(sum+1,sum+len+1,aaa); for(int i=1;i<=len;i++) { rebuild(); int t=sum[i].b; if(k[t]==1)continue; k[t]=1; k[re[t]]=1; double w=dinic()+e[t].flow; if(w+ecp>=xxx&&w-ecp<=xxx){xxx-=e[t].flow;ans[++top]=e[t].hh;} else k[t]=0,k[re[t]]=0; } printf("%d\n",top); sort(ans+1,ans+top+1); for(int i=1;i<=top;i++) { cout<<ans[i]<<‘ ‘; } cout<<endl; return ; } void initx() { n=read();m=read(); st=1;ed=n; for(int i=1;i<=m;i++) {a[i]=read();b[i]=read();c[i]=read();} return ; } int main() { initx(); work1(); work2(); return 0; }
oj1638
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。