1585: [Usaco2009 Mar]Earthquake Damage 2 - #include <Seter> - using namespace Orz;
1585: [Usaco2009 Mar]Earthquake Damage 2
http://www.zybbs.org/JudgeOnline/problem.php?id=1585
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 143618 | Seter | 1585 | Accepted | 2760 kb | 100 ms | C/Edit | 1548 B | 2011-08-19 20:15:25 |
第一的那个30MS……还是PAS……是单纯形神犇还是……
一开始构图各种2。先拆除1以外的所有点，拆成入点与出点，入点连向出点边权为1。原先的每条边双向连接边权为无穷大的边建超级汇点T，对每个报告点入点（我一开始就忘了这里应该是入点，因为这个点不能被割掉）连向T边权为无穷大。然后扫一遍就能很快AC了……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | #include <stdio.h>__inline getint(){ int re=0,ch=getchar(),k; while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1; for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48; return k?-re:re;}int n,m,s,t,dis[6002],gap[23001],flow=0,delta,x,y,z,i,stp=0;struct edge{int x,y,w;struct edge *opp,*next;}*map[6002],*neck[6002],*from[6002],*cur[6002],st[92000],*f;__inline addedge(x,y,z){ st[stp^1].y=st[stp].x=x;st[stp].y=st[stp^1].x=y; st[stp].next=map[x];st[stp^1].next=map[y]; (st[stp^1].opp=map[x]=st+stp)->w=z;st[stp].opp=map[y]=st+(stp^1); stp+=2;}main(){ int k; gap[0]=n=(getint()<<1)+2; m=getint();t=getint(); for(i=n-2;i>0;i-=2)addedge(i,i^1,1); for(i=0;i<m;i++){ x=getint()<<1;y=getint()<<1; addedge(x^1,y,100000); addedge(y^1,x,100000); }while(t--)addedge(getint()<<1,0,100000); for(m+=n,i=s=3,t=0;dis[s]<=m;){ for(cur[i]||(cur[i]=map[i]);cur[i];cur[i]=cur[i]->next)if(cur[i]->w&&dis[cur[i]->y]+1==dis[i]){ neck[(from[cur[i]->y]=cur[i])->y]=s==i?cur[i]:neck[i]->w>cur[i]->w?cur[i]:neck[i]; if(t==(i=cur[i]->y)){ for(flow+=delta=neck[t]->w;i!=s;i=from[i]->x)from[i]->w-=delta,from[i]->opp->w+=delta; i=neck[t]->x; }break; }if(!cur[i]){ if(!--gap[dis[i]])break; for(dis[i]=m,f=map[i];f;f=f->next)if(f->w&&dis[f->y]<dis[i])dis[i]=dis[(cur[i]=f)->y]; gap[++dis[i]]++; i=i==s?s:from[i]->x; } }printf("%d\n",flow); return 0;} |
By Seter
评论 (0)