bzoj 1312 最大密度子图

晕，m=0是要输出1（弄的我还找管理员要数据，但明显题意是叫我们输出0呀）

最大密度子图，把边转换成点，然后二分答案，跑最大权闭合子图判定是否可行。

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 #define N 1110

 #define oo 0x3f3f3f3f

 using namespace std;

 struct Edge {

     int u, v, f;

     Edge( int u, int v, int f ):u(u),v(v),f(f){}

 };

 int gcd( int a, int b ) {

     return b?gcd(b,a%b):a;

 }

 struct Pair {

     int a, b;

     Pair( int aa, int bb ) {

         int cd = gcd(aa,bb);

         a=aa/cd;

         b=bb/cd;

     }

     bool operator<( const Pair &o ) const {

         return a*o.b < o.a*b;

     }

     bool operator==( const Pair &o ) const {

         return a*o.b==o.a*b;

     }

 };

 int n, m;

 vector<Edge> edge;

 vector<int> g[N];

 vector<Pair> prs;

 int dep[N], cur[N], qu[N], bg, ed;

 int uu[N], vv[N], idx[N], src, dst, idc;

 bool vis[N];

 void init() {

     for( int i=; i<=dst; i++ )

         g[i].clear();

     edge.clear();

 }

 void adde( int u, int v, int f ) {

     g[u].push_back( edge.size() );

     edge.push_back( Edge(u,v,f) );

     g[v].push_back( edge.size() );

     edge.push_back( Edge(v,u,) );

 }

 bool bfs() {

     memset( dep, , sizeof(dep) );

     qu[bg=ed=] = src;

     dep[src] = ;

     while( bg<=ed ) {

         int u=qu[bg++];

         for( int t=; t<g[u].size(); t++ ) {

             Edge &e=edge[g[u][t]];

             if( e.f && !dep[e.v] ) {

                 dep[e.v]=dep[e.u]+;

                 qu[++ed] = e.v;

             }

         }

     }

     return dep[dst];

 }

 int dfs( int u, int a ) {

     if( u==dst || a== ) return a;

     int remain=a, past=, na;

     for( int &t=cur[u]; t<g[u].size(); t++ ) {

         Edge &e=edge[g[u][t]];

         Edge &ve=edge[g[u][t]^];

         if( e.f && dep[e.v]==dep[e.u]+ && (na=dfs(e.v,min(e.f,remain))) ) {

             remain -= na;

             past += na;

             e.f -= na;

             ve.f += na;

             if( !remain ) break;

         }

     }

     return past;

 }

 int maxflow() {

     int flow = ;

     while( bfs() ) {

         memset( cur, , sizeof(cur) );

         flow += dfs(src,oo);

     }

     return flow;

 }

 void makeid() {

     src = n+m+;

     dst = src+;

     idc = n;

     for( int i=; i<=m; i++ ) idx[i] = ++idc;

 }

 void rebuild( int a, int b ) {

     init();

     for( int i=; i<=m; i++ ) {

         adde( src, idx[i], b );

         adde( idx[i], uu[i], oo );

         adde( idx[i], vv[i], oo );

     }

     for( int i=; i<=n; i++ )

         adde( i, dst, a );

 }

 bool ok( int a, int b ) {

     rebuild(a,b);

     return m*b-maxflow() > ;

 }

 int calc() {

     int cnt = ;

     qu[bg=ed=] = dst;

     vis[dst] = true;

     while( bg<=ed ) {

         int u=qu[bg++];

         for( int t=; t<g[u].size(); t++ ) {

             Edge &e = edge[g[u][t]^];

             if( e.f && !vis[e.u] ) {

                 vis[e.u] = true;

                 cnt += <=e.u&&e.u<=n;

                 qu[++ed] = e.u;

             }

         }

     }

     return n-cnt;

 }

 int binary() {

     for( int a=; a<=m; a++ )

         for( int b=; b<=n; b++ )

             prs.push_back( Pair(a,b) );

     sort( prs.begin(), prs.end() );

     prs.erase( unique(prs.begin(),prs.end()), prs.end() );

     int lf=, rg=prs.size()-;

     while( lf<rg ) {

         int mid = (lf+rg)>>;

         if( ok(prs[mid].a,prs[mid].b) )

             lf=mid+;

         else

             rg=mid;

     }

     ok(prs[lf].a,prs[lf].b);

     return calc();

 }

 int main() {

     scanf( "%d%d", &n, &m );

     if( m== ) {

         printf( "1\n" );

         return ;

     }

     for( int i=; i<=m; i++ )

         scanf( "%d%d", uu+i, vv+i );

     makeid();

     printf( "%d\n", binary() );

 }