2018.3.27 Test
时间：7:30~11:50
期望得分：(50+)+0+20=70
实际得分：52+5+20=77
总结
T1 看错一点题，暴力也废了很长时间。
T2 期望DP没写过不敢写，然而50分和期望没有关系，贪心什么的就行。没细看。
T3 建图死活建不出来，没想明白费用流还费了不少时间写费用流。
T1
好像很麻烦，先弃疗。
T2
代码倒很短，学学期望再写。
T3 BZOJ.4873.[六省联考2017]寿司餐厅(最小割ISAP 最大权闭合子图)
不会建图。。在最大权闭合子图和费用流徘徊，快考完发现费用流不对。。硬是把区间单独考虑了，没考虑与小区间的限制关系。
正解: 最大权闭合子图.
如果想要取一个区间，那么会把这一区间中所有的都取一遍，且一共只取一遍。
即: 选(i,j)(i<j)必选(i+1,j)和(i,j-1)；选(i,i)必选id[i]。
由源点向每个权值为正的区间连权值的边；由每个权值为负的区间向汇点连权值绝对值的边(阻碍割掉连向汇点的一边)；
用每种寿司i直接代表区间(i,i)，根据D[i,i]-id[i]的正负向汇点/源点连边；寿司向id[i]连INF的边，id[i]向汇点连m*id^2的边。
Ans = 正权和 - 最大流
//2240kb 148ms(怎么好像很慢。。)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=1e4+5,M=7e4+5,INF=0x3f3f3f3f;
int n,m,src,des,Enum,cur[N],H[N],nxt[M],fr[M],to[M],cap[M],lev[N],num[N],que[N],pre[N];
int id[105][105],A[105],d[105][105],exist[1005];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
inline void AddEdge(int u,int v,int w)
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0;
}
bool BFS()
{
for(int i=src; i<des; ++i) lev[i]=des+1;
que[0]=des, lev[des]=0; int h=0,t=1;
while(h<t)
{
int x=que[h++];
for(int i=H[x]; i; i=nxt[i])
if(lev[to[i]]==des+1 && cap[i^1])
lev[to[i]]=lev[x]+1, que[t++]=to[i];
}
return lev[src]<=des;
}
int Augment()
{
int mn=INF;
for(int i=des; i!=src; i=fr[pre[i]])
mn=std::min(mn,cap[pre[i]]);
for(int i=des; i!=src; i=fr[pre[i]])
cap[pre[i]]-=mn,cap[pre[i]^1]+=mn;
return mn;
}
long long ISAP()
{
if(!BFS()) return 0;
for(int i=src; i<=des; ++i) cur[i]=H[i],++num[lev[i]];
int x=src; long long res=0;
while(lev[src]<=des)
{
if(x==des) x=src,res+=Augment();
bool can=0;
for(int i=cur[x]; i; i=nxt[i])
if(lev[to[i]]==lev[x]-1 && cap[i])
{
can=1, cur[x]=i, pre[x=to[i]]=i;
break;
}
if(!can)
{
int mn=des;
for(int i=H[x]; i; i=nxt[i])
if(cap[i]) mn=std::min(mn,lev[to[i]]);
if(!--num[lev[x]]) break;
++num[lev[x]=mn+1];
cur[x]=H[x];
if(x!=src) x=fr[pre[x]];
}
}
return res;
}
int main()
{
n=read(),m=read(),Enum=1;
int cnt=n;
for(int i=1; i<=n; ++i) id[i][i]=i;
for(int i=1; i<n; ++i)
for(int j=i+1; j<=n; ++j) id[i][j]=++cnt;
src=0, des=cnt+n+1;
for(int i=1; i<=n; ++i)
{
A[i]=read();
if(m && !exist[A[i]]) exist[A[i]]=++cnt,AddEdge(cnt,des,/*m**/A[i]*A[i]);
if(m) AddEdge(i,exist[A[i]],INF);
}
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j) d[i][j]=read();
long long res=0;
for(int t,i=1; i<=n; ++i)
(t=d[i][i]-A[i])>0 ? res+=t,AddEdge(src,i,t) : AddEdge(i,des,-t);
for(int i=1; i<n; ++i)
for(int j=i+1; j<=n; ++j)
{
AddEdge(id[i][j],id[i+1][j],INF), AddEdge(id[i][j],id[i][j-1],INF);
d[i][j]>0 ? res+=d[i][j],AddEdge(src,id[i][j],d[i][j]) : AddEdge(id[i][j],des,-d[i][j]);
}
printf("%lld",res-ISAP());
return 0;
}
考试代码
T1
5k暴力心累（一半复制的）
刚开始想错题意了，判的点不能走。当然挺好改。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int MAXIN=1e6;
int T,X;
char IN[MAXIN],*SS=IN,*TT=IN;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
namespace Subtask1
{
const int N=9;
int n,cnt,pos1[1<<9],pos2[1<<9],H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];
inline void AddEdge(int u,int v)
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
}
void Pre()
{
for(int t,p,i=1; i<(1<<8); ++i)
{
t=0, p=cnt+1;
for(int j=i,l=1; j; j>>=1,++l)
if(j&1){
if(++t>2) break;
if(pos1[p]) pos2[p]=l;
else pos1[p]=l;
}
if(t==2) ++cnt;
else if(t==1) ++cnt,pos2[p]=pos1[p];
else pos1[p]=pos2[p]=0;
}
// for(int i=1; i<=cnt; ++i) printf("Pre:%d -> %d\n",pos1[i],pos2[i]);
}
void DFS(int x,int f,int t)
{
if(x==t) {can=1; return;}
for(int i=H[x]; i&&!can; i=nxt[i])
if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
}
void Calc_DFS(int x)
{
visp2[x]=1;
for(int i=H[x]; i; i=nxt[i])
if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
}
void Solve()
{
Pre();
while(T--)
{
n=read(), Enum=0;
for(int i=1; i<=n; ++i) H[i]=0;
for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);
int res=0;
for(int i=1; i<=cnt; ++i)
{
if(pos1[i]>n||pos2[i]>n) continue;
for(int j=1; j<=Enum; ++j) vis[j]=0;
for(int j=1; j<=n; ++j) visp[j]=0;
can=0, DFS(pos1[i],0,pos2[i]);
int t=pos2[i];
while(t!=pos1[i]) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
visp[pos1[i]]=1;
for(int ans,j=1; j<=cnt; ++j)
{
if(pos1[j]>n||pos2[j]>n) continue;
can=0, DFS(pos1[j],0,pos2[j]);
if(!can) continue;
for(int k=1; k<=Enum; ++k) vis2[k]=0;
for(int k=1; k<=n; ++k) visp2[k]=0;
t=pos2[j];
while(t!=pos1[j]) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
visp2[pos1[j]]=1;
ans=0;
for(int k=1; k<=n; ++k)
if(!visp[k]&&!visp2[k]) Calc_DFS(k),++ans;
if(ans>res) res=ans;
}
}
printf("%d\n",res);
}
}
}
namespace Subtask2
{
const int N=1003;
int n,p0,p1,h0,h1,H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];
inline void AddEdge(int u,int v)
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int f,int t)
{
if(x==t) {can=1; return;}
for(int i=H[x]; i&&!can; i=nxt[i])
if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
}
void Calc_DFS(int x)
{
visp2[x]=1;
for(int i=H[x]; i; i=nxt[i])
if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
}
void Solve()
{
while(T--)
{
n=read(),p0=read(),p1=read(),h0=read(),h1=read(), Enum=0;
for(int i=1; i<=n; ++i) H[i]=0;
for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);
for(int i=1; i<=Enum; ++i) vis[i]=0;
for(int i=1; i<=n; ++i) visp[i]=0;
can=0, DFS(p0,0,p1);
int t=p1;
while(t!=p0) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
visp[p0]=1;
can=0, DFS(h0,0,h1);
if(!can) {puts("0"); continue;}
for(int k=1; k<=Enum; ++k) vis2[k]=0;
for(int k=1; k<=n; ++k) visp2[k]=0;
t=h1;
while(t!=h0) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
visp2[h0]=1;
int res=0;
for(int k=1; k<=n; ++k)
if(!visp[k]&&!visp2[k]) Calc_DFS(k),++res;
printf("%d\n",res);
}
}
}
namespace Subtask3
{
const int N=1003;
int n,p0,p1,H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];
inline void AddEdge(int u,int v)
{
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS(int x,int f,int t)
{
if(x==t) {can=1; return;}
for(int i=H[x]; i&&!can; i=nxt[i])
if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
}
void Calc_DFS(int x)
{
visp2[x]=1;
for(int i=H[x]; i; i=nxt[i])
if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
}
void Solve()
{
while(T--)
{
n=read(),p0=read(),p1=read(), Enum=0;
for(int i=1; i<=n; ++i) H[i]=0;
for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);
for(int i=1; i<=Enum; ++i) vis[i]=0;
for(int i=1; i<=n; ++i) visp[i]=0;
can=0, DFS(p0,0,p1);
int t=p1;
while(t!=p0) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
visp[p0]=1;
int res=0;
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
{
can=0, DFS(i,0,j);
if(!can) continue;
for(int k=1; k<=Enum; ++k) vis2[k]=0;
for(int k=1; k<=n; ++k) visp2[k]=0;
t=j;
while(t!=i) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
visp2[i]=1;
int ans=0;
for(int k=1; k<=n; ++k)
if(!visp[k]&&!visp2[k]) Calc_DFS(k),++ans;
if(ans>res) res=ans;
}
printf("%d\n",res);
}
}
}
int main()
{
freopen("treediagram.in","r",stdin);
freopen("treediagram.out","w",stdout);
T=read(),X=read();
if(!X) Subtask1::Solve();
else if(X==2) Subtask2::Solve();
else Subtask3::Solve();
fclose(stdin);fclose(stdout);
return 0;
}
T2
直接输出0真的可以，还有5分233→_→
#include <cstdio>
#include <cctype>
#define gc() getchar()
#define mod (100003)
const int N=1e3+5;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
freopen("trennen.in","r",stdin);
freopen("trennen.out","w",stdout);
putchar('0');
fclose(stdin);fclose(stdout);
return 0;
}
T3
爆搜：
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=2e4+5,M=3e6+5,INF=0x3f3f3f3f;
int n,m,Ans,Max;
int cnt,tm[35],id[105][105],A[105],l[55555],r[55555],cost[45555],sum[105],d[105][105];
bool vis[7][7];
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
void DFS(int x,int s)
{
if(x>cnt)
{
memset(tm,0,sizeof tm);
memset(vis,0,sizeof vis);
int tmp=0;
for(int i=1; i<=cnt; ++i)
if((s>>i-1)&1)
for(int j=l[i]; j<=r[i]; ++j)
{
for(int k=j; k<=r[i]; ++k)
if(!vis[j][k])
tmp+=d[j][k], vis[j][k]=1;
++tm[A[j]];
}
for(int i=1; i<=Max; ++i) if(tm[i]) tmp-=m*i+tm[i]*i;
Ans=std::max(Ans,tmp);
}
else DFS(x+1,s), DFS(x+1,s|(1<<x-1));
}
int main()
{
freopen("sushi.in","r",stdin);
freopen("sushi.out","w",stdout);
n=read(),m=read();
for(int i=1; i<=n; ++i) Max=std::max(Max,A[i]=read()),sum[i]=sum[i-1]+A[i];
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j) d[i][j]=read();
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j) id[i][j]=++cnt,cost[cnt]=sum[j]-sum[i-1],l[cnt]=i,r[cnt]=j;
DFS(1,0);
printf("%d",Ans);
fclose(stdin);fclose(stdout);
return 0;
}
sb费用流。。（还是由最大流又改成费用流的）
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=2e4+5,M=3e6+5,INF=0x3f3f3f3f;
int n,m,src,des,Enum,H[N],nxt[M],fr[M],to[M],cap[M],cost[M],dis[N],pre[N];
int cnt,id[105][105],A[105],sum[105],d[105][105];
bool inq[N];
std::queue<int> q;
inline int read()
{
int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
inline void AddEdge(int u,int v,int w,int c)
{
printf("%d->%d cap:%d c:%d\n",u,v,w,c);
to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w, cost[Enum]=c;
to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0, cost[Enum]=-c;
}
bool SPFA()
{
memset(dis,0x3f,sizeof dis);
dis[src]=0, q.push(src);
while(!q.empty())
{
int x=q.front(); q.pop(),inq[x]=0;
for(int i=H[x]; i; i=nxt[i])
if(dis[to[i]]>dis[x]+cost[i] && cap[i])
{
dis[to[i]]=dis[x]+cost[i], pre[to[i]]=i;
if(!inq[to[i]]) q.push(to[i]),inq[to[i]]=1;
}
}
return dis[des]!=INF;
}
int MCMF()
{
int mn=INF,res=0;
for(int i=des; i!=src; i=fr[pre[i]])
mn=std::min(mn,cap[pre[i]]);
for(int i=des; i!=src; i=fr[pre[i]])
cap[pre[i]]-=mn,cap[pre[i]^1]+=mn,res+=cost[pre[i]]*mn;
for(int i=des; i!=src; i=fr[pre[i]])
printf("%d<-",i);
printf("%d flow:%d res:%d\n",src,mn,res);
return res;
}
int main()
{
freopen("sushi.in","r",stdin);
// freopen("sushi.out","w",stdout);
n=read(),m=read(),Enum=1;
for(int i=1; i<=n; ++i) A[i]=read(),sum[i]=sum[i-1]+A[i];
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j)
d[i][j]=read();
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j) id[i][j]=++cnt;
src=0, des=cnt<<1|1;
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j)
{
int t=0;
for(int k=i; k<=j; ++k)
for(int l=k; l<=j; ++l)
++t, AddEdge(id[i][j],id[k][l]+cnt,INF,0);
AddEdge(src,id[i][j],t,sum[j]-sum[i-1]);
}
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; ++j) AddEdge(id[i][j]+cnt,des,1,-d[i][j]);
long long res=0,ans=1e9;
while(SPFA()) ans=std::min(ans,res+=MCMF()),printf("%I64d\n",res);
printf("%I64d",-ans);
fclose(stdin);fclose(stdout);
return 0;
}