P1231 教辅的组成

传送门:https://www.luogu.org/problemnew/show/P1231

这是一道很不错的网络流入门题,关键在于如何建图。

首先,我们将练习册和源点连一条边权为1的边,然后若书 i 和练习册 j 可以配套,就将连一条从练习册 j 到书 i 边,当然边权还是1。同理,答案和书也是如此,最后再将答案和汇点连一条边权为1的边。

但是这么写还是会有点问题,因为经过一本书的路径可能与很多条,书就被使用了多次,显然不符合题意。这时候我们可以将书 i 拆成书 i1 和 i2,i1 和练习册连边,i2 和答案连边,这样就保证没一本书之用过一次了。

建好图后跑最大流就行了。

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<queue>
#include<vector>
using namespace std;
#define enter printf("\n")
#define space printf(" ")
#define Mem(a) memset(a, 0, sizeof(a))
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e4 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch))
{
ans = ans * + ch - ''; ch = getchar();
}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int t, n1, n2, n3; struct Edge
{
int from, to, cap, flow;
};
vector<Edge> edges;
vector<int> G[maxn << ];
void addEdge(int from, int to)
{
edges.push_back((Edge){from, to, , });
edges.push_back((Edge){to, from, , });
int sz = edges.size();
G[from].push_back(sz - );
G[to].push_back(sz - );
} int dis[maxn << ];
bool vis[maxn << ];
bool bfs()
{
Mem(vis);
queue<int> q;
q.push(); vis[] = ;
dis[] = ;
while(!q.empty())
{
int now = q.front(); q.pop();
for(int i = ; i < (int)G[now].size(); ++i)
{
Edge& e = edges[G[now][i]];
if(!vis[e.to] && e.cap > e.flow)
{
vis[e.to] = ;
dis[e.to] = dis[now] + ;
q.push(e.to);
}
}
}
return vis[t];
}
int cur[maxn << ];
int dfs(int now, int a)
{
if(now == t || !a) return a;
int flow = , f;
for(int& i = cur[now]; i < (int)G[now].size(); ++i)
{
Edge& e = edges[G[now][i]];
if(dis[e.to] == dis[now] + && (f = dfs(e.to, min(a, e.cap - e.flow))) > )
{
e.flow += f;
edges[G[now][i] ^ ].flow -= f;
flow += f; a -= f;
if(!a) break;
}
}
return flow;
} int maxflow()
{
int flow = ;
while(bfs())
{
Mem(cur);
flow += dfs(, INF);
}
return flow;
} //bool vis2[maxn]; int main()
{
n1 = read(); n2 = read(); n3 = read();
t = (n1 << )+ n2 + n3 + ; //为了防止编号重复
/*按注释掉的写法会WA掉,因为如果一本书多次输入,那么这个书
就多次拆点,这一本书就可以使用多次了 */
/* int m = read();
while(m--)
{
int x = read(), y = read();
addEdge(0, y + (n1 << 1));
addEdge(y + (n1 << 1), x);
addEdge(x, x + n1);
vis2[x] = 1;
}
m = read();
while(m--)
{
int x = read(), y = read();
if(!vis2[x]) addEdge(x, x + n1), vis2[x] = 1;
addEdge(x + n1, y + (n1 << 1) + n2);
addEdge(y + (n1 << 1) + n2, t);
}*/
int m = read();
while(m--)
{
int x = read(), y = read();
addEdge(y + (n1 << ), x);
}
m = read();
while(m--)
{
int x = read(), y = read();
addEdge(x + n1, y + (n1 << ) + n2);
}
for(int i = ; i <= n1; ++i) addEdge(i, i + n1);
for(int i = ; i <= n2; ++i) addEdge(, i + (n1 << ));
for(int i = ; i <= n3; ++i) addEdge(i + (n1 << ) + n2, t);
write(maxflow()); enter;
}
上一篇:【算法】CRF(条件随机场)


下一篇:Business talking in English