# command_block 的博客

### [图论记录]P7916 [CSP-S 2021] 交通规划（民间数据）

posted on 2021-10-29 19:54:19 | under 记录 |

$n,m\leq 500,\sum k\leq 50$ ，时限$\texttt{3s}$。

• 最小割模型

• $k=2$

• $k>2$

#include<algorithm>
#include<cstdio>
#include<queue>
#define Pr pair<int,int>
#define mp make_pair
#define fir first
#define sec second
#define MaxG 255000
#define MaxN 505
#define MaxK 105
using namespace std;
const int INF=1000000000;
struct Line{int t,l,nxt;}l[MaxG<<2];
int fir[MaxG],tl;
l[++tl]=(Line){v,len,fir[u]};fir[u]=tl;
l[++tl]=(Line){u,len,fir[v]};fir[v]=tl;
}
priority_queue<Pr> q;
int mx,dis[MaxG];
void Dijk(int s)
{
for (int i=1;i<=mx;i++)dis[i]=INF;
q.push(mp(dis[s]=0,s));
while(!q.empty()){
Pr now=q.top();q.pop();
if (dis[now.sec]!=-now.fir)continue;
int u=now.sec;
for (int i=fir[u],v;i;i=l[i].nxt)
if (dis[v=l[i].t]>dis[u]+l[i].l){
dis[v]=dis[u]+l[i].l;
q.push(mp(-dis[v],v));
}
}
}
struct Data{int id,col;}p[MaxK];
bool cmp(const Data &A,const Data &B)
{return A.id<B.id;}
int n,m,down[MaxN][MaxN],right[MaxN][MaxN]
,k,tn,s[MaxK],cost[MaxK][MaxK],dp[MaxK][MaxK];
#define pos(x,y) ((x)*(m+1)+(y)+1)
int pos2(int p){
if (p<=m)return pos(0,p);
if (p<=m+n)return pos(p-m,m);
if (p<=m+n+m)return pos(n,m+n+m-p);
return pos(2*(n+m)-p,0);
}
void solve()
{
scanf("%d",&k);
for (int i=0;i<=n;i++)down[i][0]=down[i][m]=0;
for (int j=0;j<=m;j++)right[0][j]=right[n][j]=0;
for (int i=1,x;i<=k;i++){
scanf("%d%d%d",&x,&p[i].id,&p[i].col);
int j=p[i].id;
if (j<=m)right[0][j-1]=x;
else if (p[i].id<=n+m)down[j-m-1][m]=x;
else if (p[i].id<=2*m+n)right[n][m+m+n-j]=x;
else down[2*(n+m)-j][0]=x;
}
for (int i=0;i<n;i++)
for (int j=0;j<=m;j++)
for (int i=0;i<=n;i++)
for (int j=0;j<m;j++)
sort(p+1,p+k+1,cmp);
p[k+1]=p[1];tn=0;
for (int i=1;i<=k;i++)
if (p[i].col!=p[i+1].col)
s[++tn]=pos2(p[i].id);
if (!tn){puts("0");return ;}
mx=pos(n,m);
for (int i=1;i<=tn;i++){
Dijk(s[i]);
for (int j=1;j<=tn;j++)
cost[i][j]=cost[i][j+tn]=cost[i+tn][j+tn]=dis[s[j]];
}
for (int len=2;len<=tn;len+=2)
for (int l=1;l+len-1<=tn+tn;l++){
int r=l+len-1;
dp[l][r]=INF;
for (int k=l+1;k<=r;k+=2)
dp[l][r]=min(dp[l][r],dp[l+1][k-1]+dp[k+1][r]+cost[l][k]);
}
int ans=INF;
for (int l=1;l<=tn;l++)
ans=min(ans,dp[l][l+tn-1]);
printf("%d\n",ans);
tl=0;for (int i=1;i<=mx;i++)fir[i]=0;
}
int main()
{
int T;scanf("%d%d%d",&n,&m,&T);
for (int i=1;i<n;i++)
for (int j=0;j<m;j++)
scanf("%d",&right[i][j]);
for (int i=0;i<n;i++)
for (int j=1;j<m;j++)
scanf("%d",&down[i][j]);
while(T--)solve();
return 0;
}