###### 30pts TLE+1
蒟蒻求解/kk
我的代码
```cpp
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
using std::min;
using std::queue;
using std::vector;
template<class I>
inline void read(I & x) {
char c = ' ';
x = 0;
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
}
template<class I>
inline void read(I & a, I & b) {read(a), read(b);}
template<class I>
inline void read(I & a, I & b, I & c) {read(a), read(b), read(c);}
template<class I>
inline void read(I & a, I & b, I & c, I & d) {read(a), read(b), read(c), read(d);}
struct node {
int to, v, inv;
node() {
to = v = inv = 0;
}
node(int t, int vv, int i) {
to = t,
v = vv,
inv = i;
}
};
queue<int> q;
int maxflow, dep[630000], curl[630000], s = 0, t;
vector<node> e[630000];
inline bool bfs() {
while (!q.empty())
q.pop();
memset(dep, 0, sizeof dep),
dep[s] = 1,
q.push(s);
while (!q.empty()) {
int now = q.front();
q.pop();
for (register int i = 0; i < e[now].size(); ++i)
if (e[now][i].v && !dep[e[now][i].to])
dep[e[now][i].to] = dep[now] + 1,
q.push(e[now][i].to);
}
return dep[t];
}
int dfs(int now, int cost) {
if (now == t)
return cost;
for (register int& i = curl[now]; i < e[now].size(); ++i) {
if (dep[e[now][i].to] == dep[now] + 1 && e[now][i].v) {
int x = dfs(e[now][i].to, min(cost, e[now][i].v));
if (x > 0) {
e[now][i].v -= x,
e[e[now][i].to][e[now][i].inv].v += x;
return x;
}
}
}
return 0;
}
inline void Dinic() {
while (bfs())
memset(curl, 0, sizeof curl),
maxflow += dfs(s, 2147483647);
}
inline void addedge(int u, int v, int w) {
e[u].push_back(node(v, w, e[v].size())),
e[v].push_back(node(u, 0, e[u].size() - 1));
}
int n1, n2, n3, m1, m2;
int main(void) {
read(n1, n2, n3, m1),
t = (n1 << 1) + n2 + n3 + 1;
for (register int i = 1; i <= n1; ++i)
addedge(i + n2, i + n2 + n1, 1);
for (register int i = 1; i <= n2; ++i)
addedge(s, i, 1);
for (register int i = 1; i <= n3; ++i)
addedge(i + n2 + (n1 << 1), t, 1);
for (register int i = 1, x, y; i <= m1; ++i)
read(x, y),
addedge(y, x + n2, i);
read(m2);
for (register int i = 1, x, y; i <= m2; ++i)
read(x, y),
addedge(x + n2 + n1, y + (n1 << 1) + n2, i);
Dinic(),
printf("%d\n", maxflow);
return 0;
}
```
by oneton429 @ 2020-06-11 21:52:22
TLE7个+1
超长代码
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int head[100001],cnt,n,m,s,t,maxflow,dis[100001],ans,vis,cur[100001],pp,qq;
queue<int>q;
struct node
{
int to,dis,next;
}a[1000001];
void add_edge(int from,int to,int dis)
{
a[++cnt].to=to;
a[cnt].dis=dis;
a[cnt].next=head[from];
head[from]=cnt;
}
bool bfs()
{
//cout<<"bfs"<<endl;
for(int i=1;i<=n;i++)
{
cur[i]=head[i];
dis[i]=0;
}
while(!q.empty())q.pop();
q.push(s);
dis[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=a[i].next)
{
int v=a[i].to;
if(a[i].dis&&!dis[v])
{
q.push(v);
dis[v]=dis[u]+1;
if(v==t)return 1;
}
}
}
return 0;
}
int luogu(int u,int flow_now)//返回u点使用了多少流量，flow_now为当前点可以使用的流量
{
//cout<<"dfs"<<endl;
if(u==t)
{
vis=1;
return flow_now;
}
int k=0,used=0;
for(int i=cur[u];i;i=a[i].next)
{
cur[u]=i;
int v=a[i].to;
if(a[i].dis&&dis[v]==dis[u]+1)
{
k=luogu(v,min(flow_now-used,a[i].dis));
if(!k)dis[v]=0;
a[i].dis-=k;
a[i^1].dis+=k;
used+=k;
}
}
return used;
}
int main()
{
int x,y;
cin>>n>>pp>>qq;
cnt++;
cin>>m;
for(int i=1;i<=n;i++)
{
add_edge(i,i+n,1);
add_edge(i+n,i,0);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_edge(y+2*n,x,1);
add_edge(x,y+2*n,0);
}
cin>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
add_edge(x+n,y+2*n+pp,1);
add_edge(y+2*n+pp,x+n,0);
}
for(int i=1;i<=pp;i++)
{
add_edge(2*n+pp+qq+1,i+2*n,1);
add_edge(i+2*n,2*n+pp+qq+1,0);
}
for(int i=1;i<=qq;i++)
{
add_edge(i+2*n+pp,2*n+pp+qq+2,1);
add_edge(2*n+pp+qq+2,i+2*n+pp,0);
}
s=2*n+pp+qq+1;
t=2*n+pp+qq+2;
n=2*n+pp+qq+2;
while(bfs())
{
while(1)
{
vis=0;
ans=luogu(s,0x7fffffff);
if(!ans||!vis)break;
maxflow+=ans;
}
}
cout<<maxflow;
}
```
应该只有我一百多行吧
by lei_yu @ 2020-07-03 19:39:39