[CLYZ2017]day4
猜测
soulution
100分
\(x,y\)坐标可以建二分图.
因为求的是所有合法猜测猜对的个数的最小值,所以考虑最小费用最大流.
从\(s\)向\(x_i\)连一条容量为\(x_i\)出现次数,费用为\(0\)的有向边;
从\(y_i\)向\(t\)连一条容量为\(y_i\)出现次数,费用为\(0\)的有向边;
若\((x_i,y_i)\)为特殊格子,从\(x_i\)向\(y_i\)连一条容量为\(1\),费用为\(1\)的有向边;否则,从\(x_i\)向\(y_i\)连一条容量为\(1\),费用为\(0\)的有向边.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 105
#define M 10005
#define K 100005
using namespace std;
struct graph{
int nxt,to,f,w;
}e[M];
struct point{
int e,v;
}pre[N];
bool inq[N];queue q;
int x[N],y[N],px[K],py[K],tx[K],ty[K];
int b[N][N],g[N],dis[N],n,m,s,t,cnt=1,tot;
inline void addedge(int x,int y,int f,int w){
e[++cnt].nxt=g[x];g[x]=cnt;
e[cnt].to=y;e[cnt].f=f;e[cnt].w=w;
}
inline void adde(int x,int y,int f,int w){
addedge(x,y,f,w);addedge(y,x,0,-w);
}
inline bool spfa(int u){
for(int i=1;i<=t;++i)
dis[i]=M;
q.push(u);dis[u]=0;inq[u]=true;
while(!q.empty()){
u=q.front();q.pop();inq[u]=false;
for(int i=g[u];i;i=e[i].nxt)
if(e[i].f>0&&dis[u]+e[i].w 开房间
60分
\(f[i][j][k](j
\(f[i][j][k]=min\{f[i-1][l][q]+|j-l|+|k-q|\}+t_{i,l}+t_{i,q}(j
\(ans=min\{f[n][j][k]\}(j
100分
类似完全背包那样优化.
\(f[i][j][k]=min\{f[i-1][j][k],f[i][j-1][k],f[i][j+1][k],f[i][j][k-1],f[i][j][k+1]\}\).
通过注意枚举顺序,还可以把\(i\)那一维压掉.
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 305
#define INF 600000000
using namespace std;
int f[N][N],t[N][N],n,m,k,ans;
inline int min(int x,int y){
return xj;--l)
f[j][l]=min(f[j][l],min(f[j+1][l],f[j][l+1])+k);
for(int j=1;j<=m;++j)
for(int l=j+1;l<=m;++l)
f[j][l]+=t[i][j]+t[i][l];
}
ans=INF;
for(int i=1;i<=m;++i)
for(int j=i+1;j<=m;++j)
ans=min(ans,f[i][j]);
printf("%d\n",ans);
}
int main(){
freopen("room.in","r",stdin);
freopen("room.out","w",stdout);
Aireen();
fclose(stdin);
fclose(stdout);
return 0;
}