題意
https://vjudge.net/problem/CodeForces-1230C
給了你總共有21張多米諾骨牌，每張牌有兩個面，然后給你一個無向圖，保證沒有環和一個頂點多條邊的情況存在，現在讓你在這個圖中的每個邊放多米諾骨牌，有一個放置規則，問你最多能放幾張多米諾骨牌上去， 放置規則就是，每個點的權值都是一樣的，你在每條邊上放的多米諾骨牌，因為它有兩個面，需要保證兩個面上面的大小就是它指向的點的權值，
如
4 4 1 2 2 3 3 4 4 1
Here is an illustration of Anadi's graph from the first sample test:
And here is one of the ways to place a domino on each of its edges:
思路
建議直接看樣例，題意就理解了，
當n<7時，顯然所有邊都能滿足，
當n==7時，列舉兩個點取值相同，然后求這兩個點共同連的點數（不合法的情況），用m減去這個最小值即可，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
int g[8][8];
int main()
{
std::ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u][v]=g[v][u]=1;
}
if(n<7)
{
cout<<m<<endl;
return 0;
}
int mn=inf;
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
int t=0;
for(int k=1;k<=n;k++)
{
if(g[i][k]&&g[k][j])
{
t++;
}
}
mn=min(t,mn);
}
}
cout<<m-mn<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/119228.html
標籤：其他
上一篇：Hadoop程式運行一直卡到INFO mapreduce.Job: Running job: job_1578474456005_0034