洛谷$P3749$ [六省联考2017] 寿司餐厅 网络流
正解:网络流
解题报告:
这道题好烦昂,,,就给了好多变量,,,但仔细读一遍题还是能$get$的所以我就不再提取一遍题目大意辣$QwQ$?
显然考虑建两排点,一排收益一排支出然后最小流呗?
考虑连边?寿司和编号之间连$inf$嘛,编号和$T$连$m\cdot x^{2}$嘛,然后关于这个$c\cdot x$显然可以归结到每个寿司上不用通过编号背锅嘛$QwQ$.最后关于那个区间的考虑强制性就说如果选了$[l,r]$就还强制选$[l,r-1]$和$[l+1,r]$所以连个$inf$边嘛,然后就欧克了?仔细想下发现似乎很正确的样子于是就做完辣$QwQ$
最后总结下怎么建边趴$QwQ$,就首先建两排点,然后每个区间$[l,r]$作一个点,每个编号作一个点,然后收益的放一边支出的放一遍,分别和$ST$连收益/支出,然后每个寿司向编号连$inf$边,每个区间向相应的必选区间连$inf$边
跑个最小割,做完辣$QwQQQQQ$!
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define gc getchar()
#define t(i) edge[i].to
#define w(i) edge[i].wei
#define n(i) edge[i].nxt
#define ri register int
#define rb register int
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)
#define my(i,x,y) for(ri i=x;i>=y;--i)
#define e(i,x) for(ri i=head[x];~i;i=n(i))
const int N=100000+50,M=40+10,inf=1e8;
int n,m,dep[N],head[N],cur[N],S,T,ed_cnt=-1,as;
bool vis[N];
struct ed{int to,nxt,wei;}edge[N<<1];
il int read()
{
rc ch=gc;ri x=0;rb y=1;
while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
if(ch=='-')ch=gc,y=0;
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
return y?x:-x;
}
il int nam(ri l,ri r){return (l-1)*n+r+1000;}
il void ad(ri x,ri y,ri z)
{edge[++ed_cnt]=(ed){x,head[y],z};head[y]=ed_cnt;edge[++ed_cnt]=(ed){y,head[x],0};head[x]=ed_cnt;}
il bool bfs()
{
queue<int>Q;Q.push(S);memset(dep,0,sizeof(dep));dep[S]=1;
while(!Q.empty())
{
ri nw=Q.front();Q.pop();
e(i,nw)if(w(i) && !dep[t(i)]){dep[t(i)]=dep[nw]+1,Q.push(t(i));if(t(i)==T)return 1;}
}
return 0;
}
il int dfs(ri nw,ri flow)
{
if(nw==T || !flow)return flow;ri ret=0;
for(ri &i=cur[nw];~i;i=n(i))
if(w(i) && dep[t(i)]==dep[nw]+1)
{ri tmp=dfs(t(i),min(flow,w(i)));ret+=tmp,w(i)-=tmp;w(i^1)+=tmp,flow-=tmp;}
return ret;
}
il int dinic(){ri ret=0;while(bfs()){rp(i,S,T)cur[i]=head[i];while(int d=dfs(S,inf))ret+=d;}return ret;}
int main()
{
//freopen("3749.in","r",stdin);freopen("3749.out","w",stdout);
n=read();m=read();S=0;T=n*n+1000+1;memset(head,-1,sizeof(head));
rp(i,1,n){ri tmp=read(),id=nam(i,i);if(!vis[tmp])ad(T,tmp,m*tmp*tmp),vis[tmp]=1;ad(tmp,id,inf);ad(T,id,tmp);}
rp(i,1,n)
rp(j,i,n)
{
ri tmp=read(),id1=nam(i,j),id2=nam(i,j-1),id3=nam(i+1,j);
if(i!=j)ad(id2,id1,inf),ad(id3,id1,inf);
if(tmp>0)ad(id1,S,tmp),as+=tmp;else ad(T,id1,-tmp);
}
// printf("as=%d\n",as);
printf("%d\n",as-dinic());
return 0;
}