題意：有n個人和m到題目，每個人做對的概率以矩陣形式給出，問如何分配才可以使做對的概率最大，有一個限制條件是做到目前為止每兩個人的做題數量差距不能超過1，也就是前n道題目，必須一人做一個
思路：網上都是dp多一點，用網絡流也可以，不過麻煩很多，可是本弱是一點dp都不會的選手啊，只能用網絡流了，對於那個限制條件，我們可以以前n道題建一次圖，然後再來n個，不過就直接建完就可以了，然後我們要求的是什麼呢，很明顯是最大權，而最大費用最大流剛好可以解決，這裡面的費用流有兩種方法，用spfa找最短路或者用dijkstra找最短路，用spfa會方便很多，因為它可以處理帶負的權值邊，dijkstra不可以，這道題就是要講權值變負，求最小費用最大流，然後將結果取負就可以了，本弱喜歡用dijkstra，處理的很麻煩，有興趣的可以看看，建議用spfa
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const double inf=1000.0;
const int maxn=1050;
typedef pair P;
struct edge{
int to,cap,rev;
double cost;
edge();
edge(int a,int b,double c,int d){to=a,cap=b,cost=c,rev=d;};
};
vectorG[maxn];
double h[maxn],dis[maxn];
int prevv[maxn],preve[maxn];
void addedge(int st,int en,int cap,double cost){
G[st].push_back(edge(en,cap,cost,G[en].size()));
G[en].push_back(edge(st,0,-cost,G[st].size()-1));
}
double min_cost_flow(int st,int en,int f){
double ans=0;
memset(h,0,sizeof(h));
while(f>0){
priority_queue,greater >que;
for(int i=0;i0&&dis[e.to]>dis[v]+e.cost+h[v]-h[e.to]){
dis[e.to]=dis[v]+e.cost+h[v]-h[e.to];
prevv[e.to]=v;
preve[e.to]=i;
que.push(P(dis[e.to],e.to));
}
}
}
if(dis[en]==inf) return -1;
for(int i=0;imax1) max1=A[i][j];
A[i][j]*=-1;
}
}
max1+=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) A[i][j]+=max1;
int t=1;
while(t<=m){
for(int i=0;i
