RT,无O2 TLE30,有O2 TLE60,不知道原因,我的板子是在dinic上改的,是我的板子出了问题还是我的建模出了问题?
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v;
long long c,w,s;//Capacity Flow Cost
};
struct ssp{
const static int N=100005;
int n,m,s,t;
vector<Edge>E;
vector<int>to[N];
long long dis[N],C[N],ret;//去掉了当前弧优化 | 又加上了(
bool vis[N];
void clear(int n){
for(int i=1;i<=n;i++)
to[i].clear();
E.clear();
}
void AddEdge(int u,int v,long long w,long long s){
E.push_back({u,v,w,0,s});
E.push_back({v,u,0,0,-s});
m=E.size();
to[u].push_back(m-2);
to[v].push_back(m-1);
}
bool spfa(){
memset(dis,6,sizeof(dis));
queue<int>que;
que.push(s);
dis[s]=0;
vis[s]=1;
while(!que.empty()){
int cur=que.front();
que.pop();
vis[cur]=0;
for(int i=0;i<to[cur].size();i++){
Edge& e=E[to[cur][i]];
if(e.c>e.w&&dis[e.v]>dis[cur]+e.s){
dis[e.v]=dis[cur]+e.s;
if(!vis[e.v]){
que.push(e.v);
vis[e.v]=1;
}
}
}
}
return dis[t]<=1e15;
}
long long dfs(int u,long long v){
if(u==t||v==0)
return v;
long long w=0,f;
vis[u]=1;
for(int i=C[u];i<to[u].size()&&v;i++){
C[u]=i;
Edge& e=E[to[u][i]];
if(!vis[e.v]&&dis[u]+e.s==dis[e.v]&&(f=dfs(e.v,min(v,e.c-e.w)))>0){
ret+=f*e.s;
e.w+=f;
E[to[u][i]^1].w-=f;
w+=f;
v-=f;
}
}
vis[u]=0;
return w;
}
pair<long long,long long> MaxFaFaflow(int s,int t){
this->s=s;
this->t=t;
ret=0;
long long res=0,cur;
while(spfa()){
memset(C,0,sizeof(C));
while(cur=dfs(s,1e18))
res+=cur;
}
return make_pair(res,ret);
}
}R;
int n,m,t[50][105],sum,p[50];//每个厨师拆成sum个点
int MK(int u,int v){//第u个厨师,第v道菜
return (u-1)*sum+v;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&p[i]);
sum+=p[i];
R.AddEdge(1,i+2,p[i],0);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&t[i][j]);
for(int i=1;i<=m;i++)
for(int j=1;j<=sum;j++){
R.AddEdge(MK(i,j)+n+2,2,1,0);
for(int k=1;k<=n;k++)
R.AddEdge(k+2,MK(i,j)+n+2,1,j*t[k][i]);
}
printf("%lld",R.MaxFaFaflow(1,2).second);
}/*
*/