外国一些做环保袋的网站,wordpress 虚拟商品,2015年全球网站优秀设计师,wordpress跳转到外部链接文章目录题目描述数据范围解析代码题目描述
尼克在一家养猪场工作#xff0c;这家养猪场共有MMM间锁起来的猪舍#xff0c;由于猪舍的钥匙都给了客户#xff0c;所以尼克没有办法打开这些猪舍。有NNN个客户从早上开始一个接一个来购买生猪#xff0c;他们到达后首先用手中…
文章目录题目描述数据范围解析代码题目描述
尼克在一家养猪场工作这家养猪场共有MMM间锁起来的猪舍由于猪舍的钥匙都给了客户所以尼克没有办法打开这些猪舍。有NNN个客户从早上开始一个接一个来购买生猪他们到达后首先用手中的钥匙打开他所能打开的全部猪舍然后从中选取他要买的猪尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。
好在尼克事先知道每位客户手中有哪些钥匙要买多少猪以及客户到来的先后次序。请你写一个程序帮助尼克求出最多能卖出多少头猪。
数据范围
M1000,N100M1000,N100M1000,N100
解析
关键在于建图的方法 直观感觉是把客户和他能开的猪圈连不限流的双向边但是会出现时光倒流的bug 我的解决办法是只让猪圈和顾客连边然后顾客按先后顺序暴力判断猪圈有交集则连一条单向不限流的边 但这样的理论最差边数是n2n^2n2再加上点数为m,1e3级别最差情况下 m2∗n2m^2*n^2m2∗n2似乎无法通过 然而实际上59ms跑的飞快 所以网络流一定要敢写 一个比较巧妙的建图方式是把猪圈x连向第一个打开x的顾客以后再有打开x的顾客k就从上一个打开x的顾客lst连一条到k的不限流的边 很巧妙 不过边数最差似乎还变成了n*m,更差了…
代码
因为似乎没有实质的优化所以还是暴力建图的码
#includebits/stdc.h
#define ll long long
using namespace std;
const int N1205;
const int M1e9;
ll read(){ll x0,f1;char cgetchar();while(!isdigit(c)){if(c-) f-1;cgetchar();};while(isdigit(c)){xx*10c-0;cgetchar();}return x*f;
}
int n,m,s,t,num;
struct node{int to,nxt,cap;
}p[N*N*2];
int fi[N],cnt;
void addline(int x,int y,int cap){p[cnt](node){y,fi[x],cap};fi[x]cnt;p[cnt](node){x,fi[y],0};fi[y]cnt;
}
int col[N],cur[N];
queueintq;
int bfs(){memset(col,0,sizeof(col));col[s]1;q.push(s);while(!q.empty()){int nowq.front();q.pop();for(int icur[now]fi[now];~i;ip[i].nxt){int top[i].to;if(col[to]||!p[i].cap) continue;col[to]col[now]1;q.push(to);}}return col[t];
}
int dfs(int x,int lim){if(xt||!lim) return lim;int res0;for(int icur[x];~ilim;ip[i].nxt){int top[i].to;if(!p[i].cap||col[to]!col[x]1) continue;int adddfs(to,min(lim,p[i].cap));resadd;lim-add;p[i].cap-add;p[i^1].capadd;if(!lim) break;}if(!res) col[x]-1;return res;
}
int dinic(){int tot0;while(bfs()){while(int tmpdfs(1,2e9)) tottmp;}return tot;
}
int key[106][1005],tot[106],need[106],id[106];
bool vis[1005];
bool ok(int x,int y){memset(vis,0,sizeof(vis));for(int i1;itot[x];i) vis[key[x][i]]1;for(int i1;itot[y];i) if(vis[key[y][i]]) return true;return false;
}
int main(){memset(fi,-1,sizeof(fi));cnt-1;mread();nread();snum;tnum;for(int i1;im;i){int xread();num;addline(s,num,x);}for(int i1;in;i){tot[i]read();id[i]num;for(int j1;jtot[i];j){key[i][j]read();addline(key[i][j]2,num,2e9);}need[i]read();addline(num,t,need[i]);}for(int i1;in;i){for(int ji1;jn;j){if(ok(i,j)) addline(id[i],id[j],2e9);}}printf(%d,dinic());return 0;
}
