bzoj 1894 游戏

题目大意：

$n$个装备，每个装备有两个值，可以攻击该值对应的怪兽。每个装备最多用一次

每个怪兽被打一次之后就会死，每个怪兽可以被打当且仅当前面的都死了，求最多打多少个

思路：

很明显的二分图匹配，如果用$Dinic$的时候一条一条加入连向终点的边即可

但是为什么这道题我$TLE$了啊垃圾Dinic要你有何用，我也不(wang)会(le)匈牙利啊

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<map>

 #include<set>

 #define ll long long

 #define db double

 #define inf 2139062143

 #define MAXN 4010

 #define MOD 1000000007

 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)

 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)

 #define ren for(register int i=fst[x];i;i=nxt[i])

 #define pb(i,x) vec[i].push_back(x)

 #define pls(a,b) (a+b+MOD)%MOD

 #define mns(a,b) (a-b+MOD)%MOD

 #define mul(a,b) (1LL*(a)*(b))%MOD

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,s,t;

 struct Dinic

 {

     int fst[MAXN],nxt[MAXN<<],to[MAXN<<],val[MAXN<<],cnt;

     int S,T,vis[MAXN],tot,cur[MAXN],q[MAXN],l,r,dis[MAXN];

     Dinic(){memset(fst,,sizeof(fst));cnt=;}

     void add(int u,int v,int w) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v,val[cnt]=w;}

     void ins(int u,int v,int w) {add(u,v,w);add(v,u,);}

     int bfs()

     {

         q[l=r=]=T,vis[T]=++tot,dis[T]=;int x;

         while(l<=r)

         {

             x=q[l++];cur[x]=fst[x];ren if(vis[to[i]]!=tot&&val[i^])

                 vis[to[i]]=tot,dis[to[i]]=dis[x]+,q[++r]=to[i];

         }

         return vis[S]==tot;

     }

     int dfs(int x,int a)

     {

         if(x==T||!a) return a;int f,flw=;

         for(int& i=cur[x];i&&a;i=nxt[i])

             if(val[i]&&dis[to[i]]==dis[x]-&&(f=dfs(to[i],min(a,val[i]))))

                 val[i]-=f,val[i^]+=f,flw+=f,a-=f;return flw;

     }

     int solve(int s,int t,int res=)

         {S=s,T=t;while(bfs()) res+=dfs(S,inf);return res;}

 }D;

 int main()

 {

     n=read(),m=read(),s=,t=n+m+;int a,b;rep(i,,m)

         {a=read()+,b=read()+;D.ins(a,i+n,);D.ins(b,i+n,);}

     rep(i,,n) D.ins(s,i,);

     rep(i,,m+) {D.ins(i+n,t,);if(!D.solve(s,t)) return printf("%d\n",i-),;}

 }

bzoj 1191 代码（与此题只是数据范围区别

然后发现了奇妙的并查集做法

对每个装备的两个值连边，若形成一个$x$个点的树，则我们可以选走$x-1$个点，留下最大的那个

若成环，则都可以取。这样我们并查集合并即可，合并时找出最大的不行变成可以的

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<vector>

 #include<map>

 #include<set>

 #define ll long long

 #define db double

 #define inf 2139062143

 #define MAXN 1001000

 #define MOD 1000000007

 #define rep(i,s,t) for(register int i=(s),i##__end=(t);i<=i##__end;++i)

 #define dwn(i,s,t) for(register int i=(s),i##__end=(t);i>=i##__end;--i)

 #define ren for(register int i=fst[x];i;i=nxt[i])

 #define pb(i,x) vec[i].push_back(x)

 #define pls(a,b) (a+b+MOD)%MOD

 #define mns(a,b) (a-b+MOD)%MOD

 #define mul(a,b) (1LL*(a)*(b))%MOD

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,fa[MAXN],ok[MAXN];

 int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]);}

 int main()

 {

     n=read(),m=;int a,b;rep(i,,m) fa[i]=i;rep(i,,n)

     {

         a=find(read()),b=find(read());if(a==b) {ok[a]=;continue;}

         if(a>b) swap(a,b);ok[!ok[a]?a:b]=,fa[a]=b;

     }rep(i,,m+) if(!ok[i]) return printf("%d\n",i-),;

 }

巴特西

bzoj 1894 游戏

最新文章

热门文章