Description
小$G$非常喜欢学习，热衷于刷$GPA$。新的学期开始，他又要开始挑选课程，以便刷分了。
他的课业计划中共包含$n$项课程，每项课程都需要在$m$周中的某一周完成。课程与周数都从$1$开始编号。
一些课程有前置课程，对于所有的$i(1;leq;i;leq;k)$，$a_i$是$b_i$的前置课程。也就是修完$a_i$才能修$b_i$。
相同的课程在不同周可能会由不同教授授课，不同教授会影响小$G$在这门课上的分数。
我们用一个数组$x_{i,j}$来描述这个信息，对于每项课程$i$和周数$j$，$x_{i,j}$表示在第$j$周修第$i$门课所能得到的分数。如果$x_{i,j}=−1$则说明那周不能修这门课。
一周中可以修多门课，而一门课需要用一整周的时间才算修完。
请帮助小$G$修完所有课程，并使得他得到分数的平均值最大吧。
Input
第一行三个整数$n,m,k$，表示课程数、总周数与前置课程关系数。
接下来$n$行，每行$m$个整数，第$i$行第$j$个数表示$x_{i,j}$。
接下来$k$行，每行包含两个整数$a_i,b_i$。
Output
输出一个实数，表示所能得到的$n$门课程分数平均值的最大值。答案保留两位小数。
Sample Input
4 5 4
20 -1 100 -1 -1
100 30 -1 -1 -1
100 -1 30 20 40
100 30 40 50 20
1 2
1 3
2 4
3 4
Sample Output
32.50
HINT
$1;leq;n,m;leq;100,0;leq;k;leq;100,−1;leq;x_{i,j};leq;100,1;leq;a_i,b_i;leq;n$.
Solution
总数不变,平均值最大即总和最大,考虑用网络流求解.
先将每个课程$i$按完成的的日期$d$拆成点$<i,d>$.
从$s$向$<i,0>$连一条容量为$+infty$的有向边,
从$<i,m>$向$t$连一条容量为$+infty$的有向边,
从$<i,d>$向$<i,d+1>$连一条容量为$100-x_{i,d+1}$的有向边($din[0,m)$),
从$<a_i,d>$向$<b_i,d+1>$连一条容量为$+infty$的有向边($din[0,m)$).
跑最小割$mincut$,答案为$frac{100n-mincut}{n}$.
#include<cmath> #include<ctime> #include<queue> #include<stack> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define K 105 #define N 10105 #define M 40405 #define INF 1000000000 using namespace std; struct graph{ int nxt,to,f; }e[M]; int x[K][K],g[N],dep[N],n,m,k,s,t,cnt; queue<int> q; inline void addedge(int x,int y,int f){ e[++cnt].nxt=g[x];g[x]=cnt;e[cnt].to=y;e[cnt].f=f; } inline void adde(int x,int y,int f){ addedge(x,y,f);addedge(y,x,0); } inline bool bfs(int u){ memset(dep,0,sizeof(dep)); dep[u]=1;q.push(u); while(!q.empty()){ u=q.front();q.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f>0&&!dep[e[i].to]){ q.push(e[i].to); dep[e[i].to]=dep[u]+1; } } return dep[t]; } inline int dfs(int u,int f){ int ret=0; if(u==t) return f; for(int i=g[u],d;i&&f;i=e[i].nxt) if(e[i].f>0&&dep[e[i].to]>dep[u]){ d=dfs(e[i].to,min(f,e[i].f)); ret+=d;f-=d;e[i].f-=d;e[i^1].f+=d; } if(!ret) dep[u]=-1; return ret; } inline int dinic(){ int ret=0; while(true){ if(!bfs(s)) return ret; ret+=dfs(s,INF); } } inline void Aireen(){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;++i) for(int j=0;j<=m;++j) x[i][j]=++cnt; s=++cnt;t=++cnt; cnt=1; for(int i=1;i<=n;++i){ adde(s,x[i][0],INF); adde(x[i][m],t,INF); } for(int i=1,y;i<=n;++i) for(int j=0;j<m;++j){ scanf("%d",&y); if(y<0) adde(x[i][j],x[i][j+1],INF); else adde(x[i][j],x[i][j+1],100-y); } for(int i=1,a,b;i<=k;++i){ scanf("%d%d",&a,&b); for(int j=0;j<m;++j) adde(x[a][j],x[b][j+1],INF); } printf("%.2lf ",100.0-(double)(dinic())/(double)(n)); } int main(){ freopen("select.in","r",stdin); freopen("select.out","w",stdout); Aireen(); fclose(stdin); fclose(stdout); return 0; }