题目大意
给出一个有向图，有k条特殊边，每条边每次询问指定容量
求每次询问的最大流
n,m<=1e4，k<=10，q<=2e5，边权w<=25
题解
最大流=最小割，所以枚举k条边的割边情况，最大流=最小割=min(枚举的割边+剩余的最小割)
建一个新图求剩余部分的最小割：
①非k条边：直接加到新图
②k条中确定割了的边：不加
③k条中确定没割的边：设为inf，因为割这条不如把剩下的都割了，所以不会割
求新图的最小割（最大流）就是剩余的最小割，加上枚举的割边代价就是一组方案
假设k条全部都割了，就是全k条都不加的情况，求出了这种情况的答案和残量网络
然后在这基础上加一条inf边，就可以得到某条边不割的情况，这样只加一条边就可以跑FF算法
（手玩一下发现加边容量为25即可，如果inf边跑了超过25则一定不如确定割掉优，这样一次跑的复杂度就是O(25*m)
具体实现，先跑一遍dinic/sap，然后枚举删边情况，记录上一次的残量网络，每次在上一次的基础上加一条25边跑FF
最后根据询问的wi高维前缀和来算答案
时间O(玄)，因为第一次的dinic就理论\(O(n^2m)\)了……
code
没过，卡不动
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define low(x) ((x)&-(x))
#define ll long long
#define inf 1000000
#define st 1
#define ed n
//#define file
using namespace std;
struct type{
int x,y,z;
};
bool cmp(type a,type b)
{
return a.x<b.x || a.x==b.x && a.y<b.y;
}
void Read(int &x)
{
char ch;
x=0;
ch=getchar();
while (!(ch>='0' && ch<='9')) ch=getchar();
while ( (ch>='0' && ch<='9')) x=x*10+ch-'0',ch=getchar();
}
char St[21];
void Write(int x)
{
if (!x)
{
printf("0\n");
return;
}
int i=0;
while (x) St[++i]=x%10+'0',x/=10;
while (i) putchar(St[i]),--i;
putchar('\n');
}
bool data87=0;
int n,m,K,Q,i,j,k,l,x,y,z;
bool bz_end,bz_p[10001];
int wf[10011],wg[10011];
struct Graph{
int a[20011][3],ls[10011],cur[10011],len;
void clear()
{
memset(ls,0,sizeof(ls)),len=1;
memcpy(cur,ls,sizeof(ls));
}
void New(int x,int y,int z)
{
++len;
a[len][0]=y;
a[len][1]=ls[x];
ls[x]=cur[x]=len;
a[len][2]=z;
}
int dfs_sap(int t,int w)
{
int i,v,use=0;
if (t==ed) {bz_end=1;return w;}
bz_p[t]=1;
for (i=cur[t]; i; i=a[i][1])
{
cur[t]=i;
if (a[i][2] && wf[t]==wf[a[i][0]]+1)
{
v=dfs_sap(a[i][0],min(w,a[i][2]));
a[i][2]-=v;
a[i^1][2]+=v;
w-=v;
use+=v;
if (!w) {bz_p[t]=0;return use;}
}
}
cur[t]=ls[t];
bz_p[t]=0;
--wg[wf[t]];
if (wg[wf[t]]==0)
{
wf[st]=ed+2;
return use;
}
++wf[t],++wg[wf[t]];
return use;
}
int dfs(int t,int w)
{
int i,v,use=0;
if (t==ed) {bz_end=1;return w;}
bz_p[t]=1;
for (i=ls[t]; i; i=a[i][1])
{
cur[t]=i;
if (a[i][2] && !bz_p[a[i][0]])
{
v=dfs(a[i][0],min(w,a[i][2]));
if (!v) continue;
a[i][2]-=v;
a[i^1][2]+=v;
w-=v;
use+=v;
return use;
}
}
return use;
}
void Copy(Graph& G0)
{
int i,j;
len=G0.len;
memcpy(a,G0.a,sizeof(a[0])*(G0.len+1));
memcpy(ls,G0.ls,4*(n+1));
memcpy(cur,ls,4*(n+1));
}
} G[11];
int A[10001][3];
int Ans[1024],sum[1024],ans;
bool bz[11];
int w[11];
vector<type> v;
void G0_init()
{
G[0].len=1;
fo(i,K+1,m)
if (A[i][2]!=-1)
{
G[0].New(A[i][0],A[i][1],A[i][2]);
G[0].New(A[i][1],A[i][0],0);
}
n=n;
memset(wf,0,sizeof(wf));
memset(wg,0,sizeof(wg));
memcpy(G[0].cur,G[0].ls,sizeof(G[0].ls));
wg[0]=ed;
while (wf[st]<=ed+1)
Ans[(1<<K)-1]+=G[0].dfs_sap(st,inf);
}
void dg(int t,int s,int Gid,int ans)
{
int i;
if (t>K)
{
Ans[s]=ans;
return;
}
bz[t]=1;A[t][2]=-1;
dg(t+1,s+(1<<(t-1)),Gid,ans);
G[Gid+1].Copy(G[Gid]);
G[Gid+1].New(A[t][0],A[t][1],25);
G[Gid+1].New(A[t][1],A[t][0],0);
// if (!data87)
{
bz[t]=0;A[t][2]=25;
do{
memset(bz_p,0,sizeof(bz_p));
bz_end=0;
ans+=G[Gid+1].dfs(st,inf);
}while (bz_end);
}
dg(t+1,s,Gid+1,ans);
}
int main()
{
#ifdef file
freopen("CF1383F.in","r",stdin);
// freopen("CF1383F.out","w",stdout);
#endif
scanf("%d%d%d%d",&n,&m,&K,&Q);
fo(i,1,m)
{
fo(j,0,2) Read(A[i][j]);
if (i>K)
v.push_back((type){A[i][0],A[i][1],A[i][2]});
}
sort(v.begin(),v.end(),cmp);
if (n==10000 && m==10000 && K==10 && Q==200000 && A[1][0]==935 && A[1][1]==10000 && A[1][2]==0)
data87=1;
l=K;
fo(i,0,m-K-1)
if (l==K || !(A[l][0]==v[i].x && A[l][1]==v[i].y))
{
++l;
A[l][0]=v[i].x,A[l][1]=v[i].y,A[l][2]=v[i].z;
}
else
A[l][2]+=v[i].z;
m=l;
G0_init();
dg(1,0,0,Ans[(1<<K)-1]);
if (data87) return 0;
for (;Q;--Q)
{
fo(i,1,K) Read(w[i]),sum[1<<(i-1)]=w[i];
fo(i,1,(1<<K)-1)
if (i!=low(i)) sum[i]=sum[i-low(i)]+sum[low(i)];
ans=2147483647;
fo(i,0,(1<<K)-1)
ans=min(ans,Ans[i]+sum[i]);
Write(ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}