\(k=1\) 的时候显然是最小割。把一个点 \(u\) 拆成 两个点，中间连流量为 \(c_u\) 的边。
那么考虑扩展到 \(k\) 更大的情况。把上图的每个入点和出点都拆成 \(k\) 个。把节点 \(u\) 第 \(i\) 层入点和第 \(i+1\) 层入点连接，再把第 \(i\) 层入点和所有满足 \(j>i\) 层的出点连接。这样跑最小割时，割掉一条边就会上升一层，然后要从第一层源点跑到第 \(k\) 层汇点，割边的时候就会让每条路径都上升了 \(k\) 层。
#include<bits/stdc++.h>
using namespace std;
const int N=3005,M=200005,INF=2.1e9;
struct edge{
int v,nxt,f;
}e[M];
int n,m,k,fl[M],c[N],v[N],hd[N],vh[N],q[N],l,r,s,t,e_num=1,sum,cnt,to[N][10],h[N];
long long ans;
void add_edge(int u,int v,int f)
{
e[++e_num]=(edge){v,hd[u],f};
hd[u]=e_num;
e[++e_num]=(edge){u,hd[v],0};
hd[v]=e_num;
}
int bfs()
{
memset(v,0,sizeof(v));
memcpy(vh,hd,sizeof(hd));
v[q[l=r=1]=s]=1;;
while(l<=r)
{
for(int i=hd[q[l]];i;i=e[i].nxt)
if(e[i].f&&!v[e[i].v])
v[q[++r]=e[i].v]=v[q[l]]+1;
++l;
}
return v[t];
}
int dfs(int x,int fl)
{
if(x==t)
return fl;
int k;
for(int&i=vh[x];i;i=e[i].nxt)
{
if(e[i].f&&v[e[i].v]==v[x]+1&&(k=dfs(e[i].v,min(fl,e[i].f))))
{
e[i].f-=k,e[i^1].f+=k;
return k;
}
}
return 0;
}
void dinic()
{
int k;
while(bfs())
while(k=dfs(s,INF))
ans+=k;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
int p=2*n+1;
for(int i=1;i<=n;i++)
{
scanf("%d",c+i),sum+=c[i];
for(int j=0;j<k;j++)
{
add_edge(j*p+(i<<1),j*p+(i<<1|1),c[i]);
for(int a=j+1;a<k;a++)
add_edge(j*p+(i<<1),a*p+(i<<1|1),INF);
}
}
for(int i=1,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
for(int j=0;j<k;++j)
add_edge((u<<1|1)+j*p,(v<<1)+j*p,INF);
}
s<<=1;
t=((k-1)*p)+(t<<1|1);
dinic();
if(ans>sum)
return puts("-1"),0;
bfs();
for(int i=1;i<=n;i++)
for(int j=0;j<k;j++)
if(v[j*p+(i<<1)]&&!v[j*p+(i<<1|1)])
h[i]=1;
for(int i=1;i<=n;i++)
cnt+=h[i];
printf("%d\n",cnt);
for(int i=1;i<=n;i++)
if(h[i])
printf("%d ",i);
}