首页 > 代码库 > UVALive--6571--It Can Be Arranged【拆点+isap】最小割
UVALive--6571--It Can Be Arranged【拆点+isap】最小割
链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4582
题意:有n门课程,每个课程有个开始时间和结束时间,和参加人数,现要租借教室来上课。再告诉你一个矩阵,a[i][j]表示第j门课如果在第i门课后使用第i门课的教室,需要a[i][j]的时间来打扫,i的结束时间+a[i][j]必须严格小于j的开始时间。问最少需要借多少教室。
这道题的建图模型以前是做过的,和poj3469(解题报告)思路有些像,但是今天做比赛的时候没有做出来,还以为是贪心。。也想了一会如何建图,没有想出来,后来看了宝哥的代码才发现以前做过这种题,实在惭愧,这道是应该做出来的题目。以后还是得定期看自己的博客,复习以前的东西,不然都忘光了。
思路:记录每个课程都单独使用教室需要的教室数目sum,用网络流求出最多有几间教室可以共用num,sum-num就是需要的教室数量。
建图:将每个课程看作一个顶点p,将p拆为p‘和p’‘,源点向p’连弧,容量为这门课单独需要使用的教室数量rooms,p‘’向汇点连弧容量同样为rooms,对于之后输入的打扫时间矩阵a,如果i的结束时间+a[i][j]严格小于j的开始时间,则将i‘与j’‘连弧,容量为INF。这样建图,对于图中任意一个割,源点、汇点都不连通,所以每个教室的节点只会连向源点、汇点其中之一,即保证了每个课程都有教室。求出此网络的最大流,等同于最小割,表示的是最多有多少个房间能共用。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 101000 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct node{ int u,v,w,next; }edge[500000]; int head[220],dist[220],cur[220],fa[220],num[220],vis[220]; int n,m,k,cnt,nn,src,sink; void add_edge(int a,int b,int c){ edge[cnt].u = a; edge[cnt].v = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } void bfs() { int x,i,j; queue<int> q; memset(dist,-1,sizeof(dist)); q.push(sink); dist[sink] = 0; while(!q.empty()){ x = q.front(); q.pop(); for(i=head[x];i!=-1;i=edge[i].next){ if(dist[edge[i].v]<0){ dist[edge[i].v] = dist[x] + 1; q.push(edge[i].v); } } } } int augment() { int x=sink,a=INF; while(x!=src){ a = min(a,edge[fa[x]].w); x = edge[fa[x]].u; } x=sink; while(x!=src){ edge[fa[x]].w -= a; edge[fa[x]^1].w += a; x = edge[fa[x]].u; } return a; } int isap() { int i,x,ok,minm,flow=0; memset(num,0,sizeof(num)); bfs(); for(i=0;i<=nn+5;i++) if(dist[i]!=-1) num[dist[i]]++; for(i=0;i<=nn+5;i++) cur[i] = head[i]; x=src; while(dist[src]<nn){ if(x==sink){ flow += augment(); x = src; } ok=0; for(i=cur[x];i!=-1;i=edge[i].next){ if(edge[i].w && dist[x]==dist[edge[i].v]+1){ ok=1; fa[edge[i].v] = i; cur[x] = i; x = edge[i].v; break; } } if(!ok){ minm = nn + 5; for(i=head[x];i!=-1;i=edge[i].next) if(edge[i].w && dist[edge[i].v]<minm) minm=dist[edge[i].v]; if(--num[dist[x]]==0)break; num[dist[x]=minm+1]++; cur[x]=head[x]; if(x!=src) x=edge[fa[x]].u; } } return flow; } struct node1{ int s,t,num; }a[120]; int main(){ int i,j,t,cas=1; int b,c; scanf("%d",&t); while(t--){ memset(head,-1,sizeof(head)); cnt = 0; scanf("%d%d",&n,&m); src = http://www.mamicode.com/0;>UVALive--6571--It Can Be Arranged【拆点+isap】最小割