[LA 3942]Remember the Word
Trie第一题……
首先，容我吐槽一下UVa这个OJ，速度特别感人（同学们可以实践一下）。
这个题最容易想到的是[tex]O(n^2)[/tex]的DP——对于[tex]S[i\ldots n][/tex]，枚举其前缀查是否为单词，然后转移。但是啊……对于[tex]n\le 300000[/tex]这种方法肯定会T飞。
然后我们可以考虑使用Trie优化DP。对于每个[tex]S[i\ldots n][/tex]，在前缀树中查找之，就能找到所有可以作为其前缀的单词。由于每个单词最大长度也只是100，所以查找会很快辣~
代码：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=300005;
const int maxW=4005,maxL=105;
const int MOD=20071027;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define DREP(i,n) for(i=(n)-1;i>=0;i--)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
int n;
vector<int> AnsList;
namespace Trie{
const int maxnode=400005;
const int sigma_siz=26;
int Tree[maxnode][sigma_siz];
int val[maxnode];
int siz;
inline int idx(char c){
return c-'a';
}
inline void InitTrie(){
siz=0;
val[0]=0;
CL_ARR(Tree[0],0);
}
void Insert(char *s,int v){
register int u=0,n=strlen(s);
register int i,c;
REP(i,n){
c=idx(s[i]);
if(!Tree[u][c]){
siz++;
Tree[u][c]=siz;
val[siz]=0;
CL_ARR(Tree[siz],0);
}
u=Tree[u][c];
}
val[u]=v;
}
void Query(char *s,int len){
register int i,c,u=0;
AnsList.clear();
REP(i,len){
if(!s[i])
break;
c=idx(s[i]);
if(!Tree[u][c])
break;
u=Tree[u][c];
if(val[u])
AnsList.push_back(val[u]);
}
}
};
char Text[maxn];
int len[maxW];
char buf[maxL];
int d[maxn];
int main(){
register int i,j,Case=0;
int m;
while(scanf("%s%d",Text,&m)==2){
Case++;
n=strlen(Text);
Trie::InitTrie();
REP_B(i,m){
scanf("%s",buf);
len[i]=strlen(buf);
Trie::Insert(buf,i);
}
d[n]=1;
DREP(i,n){
d[i]=0;
Trie::Query(Text+i,n-i);
REP(j,AnsList.size()){
d[i]=(d[i]+d[i+len[AnsList[j]]])%MOD;
}
}
printf("Case %d: %d\n",Case,d[0]);
}
return 0;
}
[BZOJ 2081]Beads
Hash第一题……
这个题直接枚举串长Hash判断即可。不过，注意读题。
感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣！
代码：
/**************************************************************
Problem: 2081
User: danihao123
Language: C++
Result: Accepted
Time:5636 ms
Memory:10904 kb
****************************************************************/
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
register int i;
for(i=n;i>=1;i--){
sufHash[i]=s[i]+sufHash[i+1]*x;
}
for(i=1;i<=n;i++){
preHash[i]=s[i]+preHash[i-1]*x;
}
x_pow[0]=1;
for(i=1;i<=n;i++){
x_pow[i]=x*x_pow[i-1];
}
}
inline ull Hash(int i,int L){
return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
register int i,ans=0;
register ull h;
S.clear();
for(i=1;(i+k-1)<=n;i+=k){
h=Hash(i,k)*FilpHash(i,k);
if(!S.count(h)){
S.insert(h);
ans++;
}
}
if(ans>tot){
tot=ans;
AnsList.clear();
AnsList.push_back(k);
}else{
if(ans==tot)
AnsList.push_back(k);
}
}
int main(){
register int i,ans=0,maxv=0,cnt,temp;
bool flag;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%llu",&s[i]);
InitHash();
for(i=1;i<=n;i++){
Check(i);
}
printf("%d %d\n",tot,AnsList.size());
flag=false;
for(i=0;i<AnsList.size();i++){
if(flag)
putchar(' ');
flag=true;
printf("%d",AnsList[i]);
}
putchar('\n');
return 0;
}
[BZOJ 2118]墨墨的等式
论如何把数论乱搞和图论乱搞出在一起……
这个题由于要求[tex]x\ge 0[/tex]，所以不能gcd乱搞。我们可以先取[tex]\{a_n\}[/tex]的最小值[tex]p[/tex]（忽略为0的情况，为啥取最小值待会再说），对方程两边模[tex]p[/tex]。然后对于任何能使某个同余方程成立的[tex]\{x_n\}[/tex]，将其中所有[tex]x_i[/tex]同时加任意个[tex]p[/tex]，同余方程都成立。
取模后，[tex]B\in Z_p[/tex]，所以说只要对于[tex]Z_p[/tex]中的每个数找出最小的一组合法解即能推出其他解（所以说，剩余系越少效率越高，这也就要求取的[tex]a_i[/tex]要小）。不过这个最小的一组合法解怎么找？
我们先找出任意一个合法[tex]B[/tex]（比如说0吧），然后尝试加上[tex]a_i[/tex]，就可以推出其他[tex]B\in Z_p[/tex]的最小解。这个应用当然是需要最短路辣。
求出来的最短路，表示的是取最小解时的[tex]B[/tex]。这样的话就可以推出某个前缀区间中合法[tex]B[/tex]的个数（能加多少[tex]p[/tex]，就有多少个，注意不要忽略加0个的情况），并且答案符合区间减法，最后做差分即可。
注意忽略[tex]a_i=0[/tex]的情况（相当于不存在）。
代码：
/**************************************************************
Problem: 2118
User: danihao123
Language: C++
Result: Accepted
Time:1952 ms
Memory:5508 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#ifdef DEBUG
#include <cassert>
#endif
using namespace std;
typedef long long ll;
const int maxn=15;
const ll INF=0x7f7f7f7f7f7f7f7f;
ll A[maxn];
bool inQueue[500005];
ll d[500005];
int n;
ll minv;
inline void SPFA(){
register int i,u,to;
queue<int> Q;
memset(d,0x7f,sizeof(d));
d[0]=0;
Q.push(0);
inQueue[0]=true;
#ifdef DEBUG
assert(d[1]==INF);
#endif
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=1;i<=n;i++){
to=(u+A[i])%minv;
if(d[u]<INF && d[u]+A[i]<d[to]){
d[to]=d[u]+A[i];
if(!inQueue[to]){
Q.push(to);
inQueue[to]=true;
}
}
}
}
}
inline ll Calc(ll x){
register ll ans=0;
register int i=0;
for(i=0;i<minv;i++)
if(d[i]<=x)
ans+=(x-d[i])/minv+1;
return ans;
}
int main(){
ll l,r;
register int i;
scanf("%d%lld%lld",&n,&l,&r);
minv=0x7fffffff;
for(i=1;i<=n;i++){
scanf("%d",&A[i]);
if(!A[i]){
i--;
n--;
continue;
}
minv=min(minv,A[i]);
}
SPFA();
printf("%lld\n",Calc(r)-Calc(l-1));
return 0;
}
[COGS 727]太空飞行计划
第一次做最大权闭合图……so sad
关于最大权闭合图的做法，可以参考胡伯涛前辈的《最小割模型在信息学竞赛中的应用》。不过很麻烦的事是……打印方案。
注意，割走的边要么和[tex]S[/tex]相连，要么就和[tex]T[/tex]相连。如果一条从[tex]S[/tex]到[tex]E_i[/tex]被割走了，那么就说明[tex]E_i[/tex]没有被选择；如果一条从[tex]I_i[/tex]到[tex]T[/tex]的边被割走了，那么就说明[tex]I_i[/tex]被选择了。
于是乎，Dinic最后一次造层次图的时候（这次最终将不能到达[tex]T[/tex]），如果某个点（除了[tex]S[/tex]和[tex]T[/tex]）被访问到了，那个点就被选择了。
最小割的结果是所有拒绝的实验的能赚的钱及所有选用的仪器消耗的钱的和。也就是说，答案就是[tex]p[/tex]的和减去最小割。
代码：
#include <cstdio>
#include <iostream>
#include <iterator>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bitset>
using namespace std;
const int maxn=211;
const int INF=0x7fffffff;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Mincut(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,INF);
}
return ans;
}
};
vector<int> AnsList;
int main(){
register int i,j,ans=0;
int m,n,p,x;
bool flag;
string line;
// ios::sync_with_stdio(false);
// cin.tie(0);
freopen("shuttle.in","r",stdin);
freopen("shuttle.out","w+",stdout);
ostream_iterator<int> output(cout," ");
scanf("%d %d\n",&m,&n);
REP_B(i,m){
getline(cin,line);
stringstream ss(line);
ss>>p;
ans+=p;
Dinic::AddEdge(0,i,p);
while(ss>>x){
Dinic::AddEdge(i,m+x,INF);
}
}
REP_B(i,n){
cin>>p;
Dinic::AddEdge(i+m,n+m+1,p);
}
ans-=Dinic::Mincut(0,n+m+1);
REP_B(i,m){
if(Dinic::vis[i]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
AnsList.clear();
REP_B(i,n){
if(Dinic::vis[i+m]){
AnsList.push_back(i);
}
}
copy(AnsList.begin(),AnsList.end(),output);
cout<<endl;
cout<<ans<<endl;
return 0;
}
[POJ 2455]Secret Milking Machine
这个题要求最大边最小，很明显要二分答案。
考虑验证谓词[tex]C(x)[/tex]。我们可以将所有边权小于等于[tex]x[/tex]的边加入图，然后判断是否有[tex]T[/tex]条从1到N的不重复路径。
不过这个怎么做呢？我们可以把边加入（注意我们要加入的边都是无向边），并把容量设为1，从1到N跑一遍最大流，就是不重复路径条数。
为什么可以这样呢？每个边容量只有1，最多只能让一条路径使用并“推送”到终点，所以从1到N的最大流就是不重复路径条数辣。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205,maxp=40005;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
inline void ClearGraph(){
register int i;
edges.clear();
m=0;
REP(i,maxn){
G[i].clear();
}
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
struct Edge{
int u,v,d;
bool operator <(const Edge& x) const{
return d<x.d;
}
};
Edge EdgePool[maxp];
int n,p,t;
inline bool Check(int x){
register int i;
Dinic::ClearGraph();
REP_B(i,p){
if(EdgePool[i].d>x)
break;
Dinic::AddEdge(EdgePool[i].u,EdgePool[i].v,1);
Dinic::AddEdge(EdgePool[i].v,EdgePool[i].u,1);
}
if((Dinic::Maxflow(1,n))<t)
return false;
else
return true;
}
int main(){
register int i,L=0,M,R=0;
scanf("%d%d%d",&n,&p,&t);
REP_B(i,p){
scanf("%d%d%d",&EdgePool[i].u,&EdgePool[i].v,&EdgePool[i].d);
R=max(R,EdgePool[i].d+1);
}
sort(EdgePool+1,EdgePool+1+p);
while(L<R){
M=L+(R-L)/2;
if(Check(M))
R=M;
else
L=M+1;
}
printf("%d\n",L);
return 0;
}
[COGS 732]试题库
这个题和那个圆桌聚餐很像。
不过注意一点，一个题如果有多种类型，那么那个题最后只能归结到一种题型中。有些同学可能就因此怀疑样例（尽管有SPJ）。
所以最后的建图就是这样：从[tex]S[/tex]向所有题目结点连一条容量为1的边，每个题目向对应题型连一条容量为1的边，每个题型向[tex]T[/tex]连一条容量为该类型题目需要数量的边。跑一遍最大流即可，当且仅当最大流为[tex]m[/tex]时有解。
输出解吧其实也不难，直接判断从题目结点出发的弧是否满载即可。注意不要把反向弧和普通弧弄混。
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1030,maxk=25;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
#define CL_ARR(x,v) memset(x,v,sizeof(x))
struct Edge{
int u,v,cap,flow;
};
namespace Dinic{
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn],cur[maxn];
int s,t;
inline bool BFS(){
register int i,u;
queue<int> Q;
CL_ARR(vis,0);
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
REP(i,G[u].size()){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
Q.push(e.v);
}
}
}
return vis[t];
}
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,temp;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
temp=DFS(e.v,min(a,e.cap-e.flow));
if(temp>0){
e.flow+=temp;
edges[G[x][i]^1].flow-=temp;
flow+=temp;
a-=temp;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
s=S;
t=T;
register int ans=0;
while(BFS()){
CL_ARR(cur,0);
ans+=DFS(s,0x7f7f7f7f);
}
return ans;
}
};
vector<int> ans[maxn];
int main(){
int k,n,u,p;
register int i,j,m=0,flow;
freopen("testlib.in","r",stdin);
freopen("testlib.out","w+",stdout);
scanf("%d%d",&k,&n);
REP_B(i,k){
scanf("%d",&u);
m+=u;
Dinic::AddEdge(i+n,k+n+1,u);
}
REP_B(i,n){
scanf("%d",&p);
Dinic::AddEdge(0,i,1);
REP_B(j,p){
scanf("%d",&u);
Dinic::AddEdge(i,n+u,1);
}
}
flow=Dinic::Maxflow(0,n+k+1);
if(flow!=m){
puts("NoSolution!");
return 0;
}
REP_B(i,n){
for(j=0;j<Dinic::G[i].size();j++){
Edge& e=Dinic::edges[Dinic::G[i][j]];
if(e.v>n && e.v<=(n+k) && e.cap==e.flow){
ans[e.v-n].push_back(i);
}
}
}
REP_B(i,k){
printf("%d:",i);
REP(j,ans[i].size()){
printf(" %d",ans[i][j]);
}
putchar('\n');
}
return 0;
}
[BZOJ 1711]吃饭
这道题当初竟然没A……so sad
这题的建图要这么来：吃的、喝的、牛什么的统统拉进图里（不过牛本身只能同时享受一种食物，所以说点容量为1，要拆成俩点）。对于吃的，从[tex]S[/tex]向每个吃的连一条边。喝的每个向[tex]T[/tex]连一条边。牛本身按照喜好连即可（注意要拆成俩点！）。
代码：
/**************************************************************
Problem: 1711
User: danihao123
Language: C++
Result: Accepted
Time:20 ms
Memory:864 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn=405,INF=0x7f7f7f7f;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int d[maxn];
int s,t;
bool BFS(){
register int i,x;
queue<int> Q;
memset(vis,0,sizeof(vis));
d[s]=0;
Q.push(s);
vis[s]=true;
while(!Q.empty()){
x=Q.front();
Q.pop();
for(i=0;i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[x]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int cur[maxn];
int DFS(int x,int a){
if(x==t || a==0)
return a;
int flow=0,f;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if(d[e.v]==d[x]+1){
f=DFS(e.v,min(a,e.cap-e.flow));
if(f>0){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
}
return flow;
}
inline int Maxflow(int S,int T){
register int ans=0;
s=S;
t=T;
while(BFS()){
memset(cur,0,sizeof(cur));
ans+=DFS(s,INF);
}
return ans;
}
};
int main(){
int N,F,D,f,d,x;
register int i,j,t;
scanf("%d%d%d",&N,&F,&D);
t=2*N+F+D+1;
for(i=1;i<=F;i++)
Dinic::AddEdge(0,i,1);
for(i=2*N+F+1;i<t;i++)
Dinic::AddEdge(i,t,1);
for(i=1;i<=N;i++)
Dinic::AddEdge(F+2*i-1,F+2*i,1);
for(i=1;i<=N;i++){
scanf("%d%d",&f,&d);
for(j=1;j<=f;j++){
scanf("%d",&x);
Dinic::AddEdge(x,2*i-1+F,1);
}
for(j=1;j<=d;j++){
scanf("%d",&x);
Dinic::AddEdge(2*i+F,F+2*N+x,1);
}
}
printf("%d\n",Dinic::Maxflow(0,t));
return 0;
}
[BZOJ 2190]仪仗队
这个题啊……有规律可循。
我们可以发现，关于答案[tex]a[/tex]有如下规律：
[tex]a+1=2\mul (\Sigma_{i=2}^{n-1}\varphi(i)+2)[/tex]
然后筛法求欧拉函数即可（我听说神犇们都用了杜教筛哎）
代码：
/**************************************************************
Problem: 2190
User: danihao123
Language: C++
Result: Accepted
Time:28 ms
Memory:976 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40005;
#define CUS_REP(i,a,b) for(i=(a);i<=(b);i++)
int phi[maxn];
int n;
void sieve(){
register int i,j;
phi[1]=1;
CUS_REP(i,2,n)
if(!phi[i])
for(j=i;j<=n;j+=i){
if(!phi[j])
phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
int main(){
register int i,ans=2;
scanf("%d",&n);
sieve();
/*
#ifdef DEBUG
CUS_REP(i,1,n)
printf("%d\n",phi[i]);
#endif
*/
CUS_REP(i,2,n-1)
ans+=phi[i];
printf("%d\n",ans*2-1);
return 0;
}
[COGS 740]分配问题
很明显是二分图最大权匹配。可以用匈牙利算法求解，但我比较弱……所以就写了个费用流。
注意最优解和最差解都要给出！
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205;
namespace MCMF{
struct Edge{
int u,v,cap,flow,cost;
};
vector<Edge> edges;
vector<int> G[maxn];
int m;
inline void AddEdge(int u,int v,int cap,int cost){
edges.push_back((Edge){u,v,cap,0,cost});
edges.push_back((Edge){v,u,0,0,-cost});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
inline void ClearGraph(){
register int i;
edges.clear();
for(i=0;i<maxn;i++)
G[i].clear();
}
int a[maxn];
bool inQueue[maxn];
int d[maxn],p[maxn];
bool BellmanFord(int s,int t,long long& cost){
register int i,u;
queue<int> Q;
memset(d,0x7f,sizeof(d));
memset(inQueue,0,sizeof(inQueue));
d[s]=0;
inQueue[s]=true;
p[s]=0;
a[s]=0x7f7f7f7f;
Q.push(s);
while(!Q.empty()){
u=Q.front();
Q.pop();
inQueue[u]=false;
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
d[e.v]=d[u]+e.cost;
p[e.v]=G[u][i];
a[e.v]=min(a[u],e.cap-e.flow);
if(!inQueue[e.v]){
Q.push(e.v);
inQueue[e.v]=true;
}
}
}
}
if(d[t]==0x7f7f7f7f)
return false;
cost+=((long long)d[t])*((long long)a[t]);
for(u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return true;
}
long long MincostMaxflow(int s,int t){
register long long ans=0;
while(BellmanFord(s,t,ans));
return ans;
}
};
int A[105][105];
int main(){
int n;
register int i,j;
freopen("job.in","r",stdin);
freopen("job.out","w+",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
scanf("%d",&A[i][j]);
MCMF::AddEdge(i,j+n,1,A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",MCMF::MincostMaxflow(0,2*n+1));
MCMF::ClearGraph();
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
MCMF::AddEdge(i,j+n,1,-A[i][j]);
}
for(i=1;i<=n;i++)
MCMF::AddEdge(0,i,1,0);
for(i=n+1;i<=2*n;i++)
MCMF::AddEdge(i,2*n+1,1,0);
printf("%lld\n",-(MCMF::MincostMaxflow(0,2*n+1)));
return 0;
}
[BZOJ 1934]善意的投票/[BZOJ 2768]冠军调查
这个是一道题啊……不过都是挺经典的问题……
建图是这样的：支持0的从[tex]S[/tex]向此点连一条容量为1的边，支持1的就向[tex]T[/tex]连一条长度为1的边，朋友之间连一条长度为1的边。跑一遍最小割即可。
这个的解释？最优情况下任何人违背自己的意见都是因为怕和朋友冲突，和朋友冲突则是因为没有违背自己的意见（废话）。所以拆了最小割就解决掉了所有冲突问题。
代码：
/**************************************************************
Problem: 2768
User: danihao123
Language: C++
Result: Accepted
Time:60 ms
Memory:7668 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=305;
namespace Dinic{
struct Edge{
int u,v,cap,flow;
};
vector<Edge> edges;
vector<int> G[maxn];
int s,t;
int m;
inline void AddEdge(int u,int v,int cap){
edges.push_back((Edge){u,v,cap,0});
edges.push_back((Edge){v,u,0,0});
m=edges.size();
G[u].push_back(m-2);
G[v].push_back(m-1);
}
bool vis[maxn];
int cur[maxn],d[maxn];
bool bfs(){
register int i,u;
queue<int> Q;
memset(vis,0,sizeof(vis));
Q.push(s);
d[s]=0;
vis[s]=true;
while(!Q.empty()){
u=Q.front();
Q.pop();
for(i=0;i<G[u].size();i++){
Edge& e=edges[G[u][i]];
if(!vis[e.v] && e.cap>e.flow){
d[e.v]=d[u]+1;
Q.push(e.v);
vis[e.v]=true;
}
}
}
return vis[t];
}
int dfs(int x,int a){
if(x==t || a==0)
return a;
int f,flow=0;
for(int& i=cur[x];i<G[x].size();i++){
Edge& e=edges[G[x][i]];
if((d[x]+1==d[e.v]) && ((f=dfs(e.v,min(a,e.cap-e.flow)))>0)){
flow+=f;
e.flow+=f;
edges[G[x][i]^1].flow-=f;
a-=f;
if(a==0)
break;
}
}
return flow;
}
int MinCut(int S,int T){
register int ans=0;
s=S;
t=T;
while(bfs()){
memset(cur,0,sizeof(cur));
ans+=dfs(s,0x7fffffff);
}
return ans;
}
};
int main(){
int n,m;
int u,v;
register int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&u);
if(!u){
Dinic::AddEdge(0,i,1);
}else{
Dinic::AddEdge(i,n+1,1);
}
}
for(i=1;i<=m;i++){
scanf("%d%d",&u,&v);
Dinic::AddEdge(u,v,1);
Dinic::AddEdge(v,u,1);
}
printf("%d\n",Dinic::MinCut(0,n+1));
return 0;
}
