QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#674768 | #9102. Zayin and Elements | ucup-team5071# | ML | 0ms | 3640kb | C++20 | 3.2kb | 2024-10-25 17:24:44 | 2024-10-25 17:24:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=3005;
struct SSP{
int cnt=1,hd[N],nxt[M<<1],to[M<<1],limit[M<<1],cst[M<<1];
void init(){
memset(hd,0,sizeof(hd));
cnt=1;
}
int add(int u,int v,int w,int c){
//cout<<u<<" "<<v<<" "<<w<<" "<<c<<endl;
nxt[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v,limit[cnt]=w,cst[cnt]=c;
nxt[++cnt]=hd[v],hd[v]=cnt,to[cnt]=u,limit[cnt]=0,cst[cnt]=-c;
return cnt-1;
}
int fr[N],fl[N],in[N],dis[N];
pair<int,int> min_cost(int s,int t){
int flow=0,cost=0;
while(true){
queue<int> q;
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
fl[s]=1e9,dis[s]=0,q.push(s);
while(!q.empty()){
int cur=q.front();
q.pop();in[cur]=0;
for(int i=hd[cur];i;i=nxt[i]){
int it=to[i],d=dis[cur]+cst[i];
// cout<<"i="<<i<<" it="<<it<<endl;
if(limit[i]&&d<dis[it]){
fl[it]=min(limit[i],fl[cur]),fr[it]=i,dis[it]=d;
if(!in[it])in[it]=1,q.push(it);
}
}
}
if(dis[t]>1e9)return {flow,cost};
flow+=fl[t],cost+=dis[t]*fl[t];
for(int u=t;u!=s;u=to[fr[u]^1])limit[fr[u]]-=fl[t],limit[fr[u]^1]+=fl[t];
}
}
}sol;
void Solve(){
int n,m;
cin>>n>>m;
int all=0;
sol.init();
int s=0,t=n+m+1;
int res=0;
for(int i=1;i<=n;i++)
sol.add(m+i,t,1,0);
vector<int> outb(m+1);
for(int i=1;i<=m;i++){
int a,b,c,siz;
cin>>a>>b>>c>>siz;
sol.add(s,i,a,0);
outb[i]=sol.add(s,i,b*2,1);
sol.add(s,i,c,2);
all+=b*2+c*2;
for(int j=1;j<=siz;j++){
int x;
cin>>x;
sol.add(i,m+x,1,0);
}
}
auto [flow,cost]=sol.min_cost(s,t);
if(flow<n){
cout<<"-1\n";return;
}
for(int i=1;i<=m;i++)if(sol.limit[outb[i]]%2){
vector<int> st(n+m+1);
function<int(int)>dfs = [&](int x){
if(x==i)return 0;
if(x<=m&&sol.limit[outb[x]]%2){
sol.limit[outb[x]]--;
return 1;
}
for(int j=sol.hd[x];j;j=sol.nxt[j])if(sol.to[j]>=1&&sol.to[j]<=n+m&&sol.limit[j]){
if(!st[sol.to[j]]&&dfs(sol.to[j])){
st[sol.to[j]]=1;
sol.limit[j]--;
sol.limit[j^1]++;
return 1;
}
}
return 0;
};
int flag=0;
for(int j=sol.hd[i];j;j=sol.nxt[j])if(sol.to[j]>m&&sol.to[j]<=n+m&&sol.limit[j]){
if(!st[sol.to[j]]&&dfs(sol.to[j])){
st[sol.to[j]]=1;
sol.limit[j]--;
sol.limit[j^1]++;
flag=1;
sol.limit[outb[i]]++;
break;
}
}
cost+=flag;
}
cout<<(all-cost)/2<<"\n";
}
int main(){
ios::sync_with_stdio(false),cin.tie(0);
int T;
cin>>T;
while(T--)Solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3640kb
input:
2 5 2 2 3 1 2 3 1 1 1 1 3 4 5 2 5 2 2 3 1 1 3 1 0 1 2 1 2
output:
5 -1
result:
ok 2 lines
Test #2:
score: -100
Memory Limit Exceeded
input:
5 9 10 0 0 10 2 3 8 0 0 10 2 4 6 0 8 2 2 2 4 0 0 10 3 1 3 8 0 4 6 2 2 3 0 8 2 3 2 6 7 0 9 1 2 1 7 0 2 8 3 1 4 9 0 7 3 1 5 0 0 10 3 5 6 9 3 10 0 9 1 1 2 0 5 5 1 1 0 1 9 1 1 0 7 3 1 1 0 7 3 0 0 0 10 0 0 6 4 1 3 0 9 1 0 0 7 3 0 0 9 1 1 2 90 20 0 6 4 12 1 4 5 22 32 64 66 67 73 87 88 89 0 1 9 12 3 8 21 3...