【过题记录】 8.3

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 5e3+100,inf = 1e18;
int n,m;
struct Node{int y,Next,v;
}e[2*N];
int len = 1,Linkk[N];
int inv[N];
int st,ed;void Insert(int x,int y,int z){e[++len] = (Node){y,Linkk[x],z};Linkk[x] = len;
}int maxf = 0;
bool vis[N];
int pre[N];
bool bfs(){queue < int > q;memset(vis,0,sizeof vis);inv[st] = inf;q.push(st); vis[st] = 1;while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y;if (e[i].v == 0) continue; if(vis[y]) continue; vis[y] = 1; inv[y] = min(inv[x],e[i].v);q.push(y); pre[y] = i;if (y == ed) return 1;}}return 0;
}void Upd(){
//	cout<<"OK";int now = ed;
//	cout<<inv[ed]<<endl;while (now != st){
//		cout<<"now = "<<now<<endl;int nowe = pre[now];e[nowe].v-=inv[ed];e[nowe^1].v+=inv[ed];now = e[nowe^1].y;}
//	cout<<"now = "<<now<<endl;maxf+=inv[ed];
//	cout<<"macf = "<<maxf<<endl;
}signed main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);cin>>m>>n; st = 1; ed = n;for (int i = 1,x,y,z; i <= m; i++)cin>>x>>y>>z,Insert(x,y,z),Insert(y,x,0);while (bfs()) Upd();cout<<maxf;return 0; 
}
/*
7 10 1 7
1 2 4
1 3 5
2 3 1
2 4 5
3 5 5
3 4 2
5 4 6
4 7 5
5 6 3
6 7 4
*/ 

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+100,inf = 1e9;
int n,m,ee;
struct Node{
int y,Next,v;
}e[2*N];
int len = 1,Linkk[N];
int maxf,inv[N];
int d[N];
int st,ed;

void Insert(int x,int y,int v){
e[++len] = (Node){y,Linkk[x],v};
Linkk[x] = len;
}

queue < int > q;
bool bfs(){
for (int i = 1; i <= n+m+2; i++) d[i] = 0;
while (q.size()) q.pop();
q.push(st); d[st] = 1;
while (q.size()){
int x = q.front(); q.pop();
for (int i = Linkk[x]; i; i = e[i].Next){
int y = e[i].y;
if (!e[i].v || d[y]) continue;
q.push(y);
d[y] = d[x]+1;
if (y == ed) return 1;
}
}
return 0;
}

int dicnic(int x,int flow){
if (x == ed) return flow;
int re = flow,k;
for (int i = Linkk[x]; i; i = e[i].Next){
int y = e[i].y;
if (!e[i].v || d[y]!=d[x]+1) continue;
k = dicnic(y,min(re,e[i].v));
if (!k) d[y] = 0;
e[i].v-=k; e[i^1].v+=k;
re-=k;
}
return flow-re;
}

int main(){
cin>>n>>m>>ee;
st = n+m+1; ed = n+m+2;
for (int i = 1; i<= n; i++) Insert(st,i,1),Insert(i,st,0);
for (int i = 1,x,y,v; i <= ee; i++)
cin>>x>>y,Insert(x,y+n,1),Insert(y+n,x,0);
for (int i = n+1; i <= n+m; i++)
Insert(i,ed,1),Insert(ed,i,0);
int flow = 0;
while (bfs())
while (flow=dicnic(st,inf)) maxf+=flow;
cout<<maxf<<endl;
return 0;
}

#include<bits/stdc++.h>
using namespace std;const int N = 2000,inf = 1e9;
int t;
int n;
struct Node{int y,Next,v;
}e[2*N];
int Linkk[N],len = 1;
bool iss[N],ish[N];
int st,ed;void Insert(int x,int y,int v){e[++len] = (Node){y,Linkk[x],v};Linkk[x] = len;
}int cnt = 0,maxf;
queue < int > q;
int d[N];bool bfs(){for (int i = 1; i <= 2*n+2; i++) d[i] = 0;while (q.size()) q.pop();q.push(st); d[st] = 1;while (q.size()){int x = q.front(); q.pop();for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y; if (!e[i].v || d[y]) continue;d[y] = d[x]+1; q.push(y);if (y == ed) return 1;} }return 0;
}
int b[N];
int dicnic(int x,int flow){if (x == ed) return flow;int re = flow,k;for (int i = Linkk[x]; i; i = e[i].Next){int y = e[i].y;if (!e[i].v || d[y]!=d[x]+1) continue;k = dicnic(y,min(re,e[i].v));if (!k) d[y] = 0;e[i].v-=k; e[i^1].v+=k;re-=k;}return flow-re;
}void Work(){scanf("%d",&n);len = 1;for (int i = 1; i <= n; i++) cin>>iss[i];for (int i = 1; i <= n; i++){int op; scanf("%d",&op);if (op != 0 && op != 1) continue;if (!iss[i]) continue;ish[i] = op;}
//	for (int i = 1; i <= n; i++) cout<<ish[i]<<endl;for (int i = 1; i <= n; i++)if (iss[i] && !ish[i]) Insert(i,i+n,1),Insert(i+n,i,0);for (int i = 1; i <= n; i++){if (iss[i] && ish[i]) continue;
//		cout<<"i = "<<i<<endl;cnt++;} st = 2*n+1; ed = 2*n+2;
//	cnt = 0;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++) scanf("%d",&b[j]);
//		if (iss[i] && ish[i]) continue; cnt++;
//		if (iss[i]) {Insert(i,i+n,1),Insert(i+n,i,0);continue;}for (int j = 1; j <= n; j++)if(b[j] == 1 && iss[j]) Insert(i,j+n,1),Insert(j+n,i,0);}for (int i = 1; i <= n; i++) if (!iss[i] || !ish[i]) Insert(st,i,1),Insert(i,st,0);for(int i = n+1; i <= 2*n; i++) if (iss[i-n]) Insert(i,ed,1),Insert(ed,i,0); int flow = 0;while (bfs())while (flow = dicnic(st,inf)) maxf+=flow;
//	cout<<maxf<<' '<<cnt<<endl;if(maxf == cnt) cout<<"^_^"<<endl; else cout<<"T_T"<<endl;maxf = 0; cnt = 0;memset(iss,0,sizeof iss); memset(ish,0,sizeof ish); memset(Linkk,0,sizeof Linkk);return;
}int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);cin>>t; while (t--) Work();return 0; 
}