首页 > 代码库 > BZOJ2502: 清理雪道
BZOJ2502: 清理雪道
题解：
裸下界最小流。j打成i感觉人生失去了希望。。。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000 14 #define maxm 100000 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define for0(i,n) for(int i=0;i<=(n);i++) 19 #define for1(i,n) for(int i=1;i<=(n);i++) 20 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 21 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 22 #define for4(i,x) for(int i=head[x],y;i;i=e[i].next) 23 #define mod 1000000007 24 using namespace std; 25 inline int read() 26 { 27 int x=0,f=1;char ch=getchar(); 28 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 29 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 30 return x*f; 31 } 32 int n,m,s,t,ss,tt,in[maxn],maxflow,tot=1,head[maxn],cur[maxn],h[maxn]; 33 queue<int>q; 34 struct edge{int go,next,v;}e[maxm]; 35 inline void ins(int x,int y,int v) 36 { 37 e[++tot]=(edge){y,head[x],v};head[x]=tot; 38 e[++tot]=(edge){x,head[y],0};head[y]=tot; 39 } 40 inline void insert(int x,int y,int l,int r) 41 { 42 in[y]+=l;in[x]-=l;ins(x,y,r-l); 43 } 44 void build() 45 { 46 for0(i,tt)if(in[i]>0)ins(ss,i,in[i]);else if(in[i]<0)ins(i,tt,-in[i]); 47 } 48 bool bfs() 49 { 50 for(int i=0;i<=tt;i++)h[i]=-1; 51 q.push(s);h[s]=0; 52 while(!q.empty()) 53 { 54 int x=q.front();q.pop(); 55 for(int i=head[x];i;i=e[i].next) 56 if(e[i].v&&h[e[i].go]==-1) 57 { 58 h[e[i].go]=h[x]+1;q.push(e[i].go); 59 } 60 } 61 return h[t]!=-1; 62 } 63 int dfs(int x,int f) 64 { 65 if(x==t) return f; 66 int tmp,used=0; 67 for(int i=cur[x];i;i=e[i].next) 68 if(e[i].v&&h[e[i].go]==h[x]+1) 69 { 70 tmp=dfs(e[i].go,min(e[i].v,f-used)); 71 e[i].v-=tmp;if(e[i].v)cur[x]=i; 72 e[i^1].v+=tmp;used+=tmp; 73 if(used==f)return f; 74 } 75 if(!used) h[x]=-1; 76 return used; 77 } 78 void dinic() 79 { 80 maxflow=0; 81 while(bfs()) 82 { 83 for (int i=0;i<=tt;i++)cur[i]=head[i];maxflow+=dfs(s,inf); 84 } 85 } 86 int minflow() 87 { 88 s=ss;t=tt; 89 dinic(); 90 int ans=e[tot].v; 91 e[tot].v=e[tot^1].v=0; 92 s=n+1;t=0; 93 dinic(); 94 return ans-maxflow; 95 } 96 int main() 97 { 98 freopen("input.txt","r",stdin); 99 freopen("output.txt","w",stdout);100 n=read();101 for1(i,n)102 {103 int x=read();104 for1(j,x)insert(i,read(),1,inf);105 }106 s=0;t=n+1;ss=t+1;tt=t+2;107 for1(i,n)insert(s,i,0,inf),insert(i,t,0,inf);108 build();109 insert(t,s,0,inf);110 printf("%d\n",minflow()); 111 return 0;112 }
2502: 清理雪道
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 127 Solved: 67
[Submit][Status]
Description
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
Input
Output
输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。
Sample Input
8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
Sample Output
4
HINT
Source
2011福建集训
BZOJ2502: 清理雪道
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。