第一版写的 hlpp 80pts,改了一个下午没有改过。然后我试着把板子改成了 Dinic 就过了??有大佬可以帮忙看看吗?
hlpp 代码我放下面了。
#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,ouye;
struct edge{
int to,nxt;
int val;
}e[10200010];
int head[10200010],tot=1;
int over[10200010],vist[10200010];
int gap[10200010],h[10200010];
struct cmp{
bool operator()(int x,int y)const{
return h[x]<h[y];
}
};
priority_queue<int,vector<int>,cmp>qq;
void add(int u,int v,int w){
e[++tot].to=v;
e[tot].nxt=head[u];
head[u]=tot;
e[tot].val=w;
e[++tot].to=u;
e[tot].nxt=head[v];
head[v]=tot;
e[tot].val=0;
}
bool bfs(){
memset(h,0x3f,sizeof h);
h[t]=0;
queue<int>q;
q.push(t);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(h[v]>h[x]+1&&e[i^1].val){
h[v]=h[x]+1;
q.push(v);
}
}
}
return (h[s]!=0x3f3f3f3f);
}
void push(int x){
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].val&&h[x]==h[v]+1){
int k=min(e[i].val,over[x]);
e[i].val-=k;
e[i^1].val+=k;
over[x]-=k;
over[v]+=k;
if(v!=s&&v!=t&&!vist[v]){
qq.push(v);
vist[v]=1;
}
if(!over[x]){
return;
}
}
}
}
void relable(int x){
h[x]=0x3f3f3f3f;
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].val&&h[x]>h[v]+1){
h[x]=h[v]+1;
}
}
}
long long hlpp(){
if(!bfs()){
return 0;
}
h[s]=2*n+1;
for(int i=1;i<=2*n+1;i++){
if(h[i]!=0x3f3f3f3f){
gap[h[i]]++;
}
}
for(int i=head[s];i;i=e[i].nxt){
int v=e[i].to;
if(e[i].val){
over[v]+=e[i].val;
e[i^1].val=e[i].val;
e[i].val=0;
if(v!=s&&v!=t&&!vist[v]){
qq.push(v);
vist[v]=1;
}
}
}
while(!qq.empty()){
int x=qq.top();
qq.pop();
vist[x]=0;
push(x);
if(over[x]){
gap[h[x]]--;
if(!gap[h[x]]){
for(int i=1;i<=2*n+1;i++){
if(i!=s&&i!=t&&h[i]>h[x]&&h[i]<=2*n+1){
h[i]=2*n+2;
}
}
}
relable(x);
gap[h[x]]++;
vist[x]=1;
qq.push(x);
}
}
return over[t];
}
long long no[5200010];
int main(){
cin>>n>>m>>ouye;
t=1;
s=2*n+1;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
add(u+n,v,0x3f3f3f3f);
add(v+n,u,0x3f3f3f3f);
}
for(int i=1,u;i<=ouye;i++){
cin>>u;
no[u]=1;
add(s,u,0x3f3f3f3f);
}
for(int i=1;i<=n;i++){
if(no[i]){
add(i,i+n,0x3f3f3f3f);
}
else{
add(i,i+n,1);
}
}
cout<<hlpp();
}